hkucuk

Dijkstra’nın Tek Kaynaklı En Kısa Yol Algoritması

14 Nisan 2022 • ☕️ 3 dk okuma • 🏷 bilgisayar, yazılım

Yazar tarafından şu dillere çevrildi: English


Dijkstra’nın tek kaynaklı en kısa yol algoritması, bir graf üzerinde bir başlangıç noktasından diğer tüm noktalara olabilecek en kısa yolları bulmaya yönelik bir algoritmadır. Bu algoritma belli bir süre içinde tüm noktalar arasında en kısa yolu bulmak için kullanılır.

Algoritmanın çalışma prensibi şu şekildedir:

  1. Başlangıç noktasının mesafesi 0 olarak belirlenir ve diğer tüm noktaların mesafesi INF (yani sonsuz) olarak ayarlanır.
  2. Graf üzerindeki tüm noktalar dolaşılır ve mesafesi olmayan (INF) en kısa nokta bulunur. Bu nokta ziyaret edilir ve mesafesi güncellenir.
  3. Ziyaret edilen noktanın bağlı olduğu diğer noktaların mesafeleri de güncellenir. Örneğin eğer ziyaret edilen noktanın mesafesi X ise ve bu noktaya bağlı bir diğer noktaya Y mesafesi var ise bu diğer noktanın mesafesi X+Y olur.
  4. Bu adım tekrar edilir ve en kısa mesafesi olmayan nokta ziyaret edilir ve mesafesi güncellenir. Bu adım tüm noktalar ziyaret edilene kadar devam eder.

Algoritma böylece tüm noktalar arasındaki en kısa yolu bulur.

Dijkstra algoritmasının önemli bir zayıf yönü bulunmaktadır, negatif ağırlıklı çizgileri işlemez. Dijkstra algoritması, ağırlıklı çizgilerin ağırlıklarının negatif olmadığını varsayar. Bu nedenle negatif ağırlıklı çizgileri işlemez ve doğru sonuçlar vermez.

GoLang dilinde, algoritmanın kodu şu şekildedir:

package main

import "fmt"

const INF = int(^uint(0) >> 1)

type Graph [][]int

func dijkstra(g Graph, source int) []int {
	distances := make([]int, len(g))
	for i := range distances {
		distances[i] = INF
	}
	distances[source] = 0

	visited := make([]bool, len(g))

	for i := 0; i < len(g); i++ {
		minDistance := INF
		var minNode int
		for j := range g {
			if !visited[j] && distances[j] < minDistance {
				minDistance = distances[j]
				minNode = j
			}
		}
		visited[minNode] = true

		for j, cost := range g[minNode] {
			if cost != 0 {
				if minDistance+cost < distances[j] {
					distances[j] = minDistance + cost
				}
			}
		}
	}

	return distances
}

func main() {
	g := Graph{
		{0, 3, 0, 2, 0},
		{3, 0, 5, 0, 6},
		{0, 5, 0, 4, 0},
		{2, 0, 4, 0, 1},
		{0, 6, 0, 1, 0},
	}
	distances := dijkstra(g, 0)
	fmt.Println(distances)
}

Program çalıştırıldığında çıktısı aşağıdaki gibi olacaktır.

> go run main.go                   
[0 3 6 2 3]

PHP dilinde algoritmanın kodu şu şekildedir:

<?php

const INF = PHP_INT_MAX;

$graph = [
    [0, 3, 0, 2, 0],
    [3, 0, 5, 0, 6],
    [0, 5, 0, 4, 0],
    [2, 0, 4, 0, 1],
    [0, 6, 0, 1, 0],
];

$source = 0;
$distances = array_fill(0, count($graph), INF);
$distances[$source] = 0;

$visited = array_fill(0, count($graph), false);

for ($i = 0; $i < count($graph); $i++) {
    $minDistance = INF;
    $minNode = -1;
    for ($j = 0; $j < count($graph); $j++) {
        if (!$visited[$j] && $distances[$j] < $minDistance) {
            $minDistance = $distances[$j];
            $minNode = $j;
        }
    }
    $visited[$minNode] = true;

    for ($j = 0; $j < count($graph); $j++) {
        if ($graph[$minNode][$j] != 0) {
            if ($minDistance + $graph[$minNode][$j] < $distances[$j]) {
                $distances[$j] = $minDistance + $graph[$minNode][$j];
            }
        }
    }
}

print_r($distances);

Kaynaklar