hkucuk

Dijkstras Kürzester-Weg-Algorithmus

14. April 2022 • ☕️ 3 min lesen • 🏷 computer, software, algorithmus, graph

Übersetzt vom autor in: Deutsch • English • Italiano • Русский


Der Single-Source-Shortest-Path-Algorithmus von Dijkstra ist ein Algorithmus zum Finden der kürzestmöglichen Pfade von einem Startpunkt zu allen anderen Punkten auf einem graph. Dieser Algorithmus wird verwendet, um den kürzesten Weg zwischen allen Punkten in einer bestimmten Zeit zu finden.

Das Funktionsprinzip des Algorithmus ist wie folgt:

  1. Der Abstand des Startpunkts wird auf 0 gesetzt und der Abstand aller anderen Punkte wird auf INF (also unendlich) gesetzt.
  2. Alle Punkte im Diagramm werden durchlaufen und der kürzeste Punkt ohne Distanz (INF) wird gefunden. Dieser Punkt wird besucht und seine Entfernung wird aktualisiert.
  3. Die Entfernungen anderer Punkte, mit denen der besuchte Punkt verbunden ist, werden ebenfalls aktualisiert. Wenn beispielsweise die Entfernung des besuchten Punkts X beträgt und es eine Entfernung Y zu einem anderen Punkt gibt, der mit diesem Punkt verbunden ist, beträgt die Entfernung dieses anderen Punkts X+Y.
  4. Dieser Schritt wird wiederholt und der Punkt ohne kürzeste Entfernung wird besucht und seine Entfernung aktualisiert. Dieser Schritt wird fortgesetzt, bis alle Punkte besucht wurden.

Der Algorithmus findet somit den kürzesten Weg zwischen allen Punkten.

Der Algorithmus von Dijkstra hat eine große Schwäche: Er verarbeitet keine negativ gewichteten Linien. Der Dijkstra-Algorithmus geht davon aus, dass die Gewichte der gewichteten Linien nicht negativ sind. Daher verarbeitet es keine negativ gewichteten Linien und liefert keine genauen Ergebnisse.

Hier ist der Code für den Algorithmus in GoLang:

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)
}

Wenn das Programm ausgeführt wird, sieht die Ausgabe wie folgt aus.

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

Der Code des Algorithmus in PHP lautet wie folgt:

<?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);

Ressourcen