Dijkstra Algorithm: Short terms and Pseudocode
Mit Hilfe des Dijkstra Algorithmus ist es möglich die kürzeste Distanz
(bzw. den geringsten Aufwand / die geringsten Kosten) zwischen einem
Anfangsknoten und einem beliebigen Knoten innerhalb eines Graphen zu bestimmen.
Funktionsweise:
Die Grundidee des
Algorithmus ist, ab einem Startknoten die kürzest möglichen Wege weiter zu
verfolgen und längere Wege beim Updaten auszuschließen. Er besteht im
wesentlichen aus diesen Schritten:
- Initialisierung aller Knoten mit der Distanz "unendlich", die des
Startknotens mit 0.
- Markierung der Distanz des Startknotens als permanent, alle anderen
Distanzen als temporär.
- Setze Startknoten als aktiv.
- Berechne die temporären Distanzen aller Nachbarknoten des aktiven Knotens
durch Addition von dessen Distanz mit den Kantengewichten.
- Wenn eine solche berechnete Distanz für einen Knoten kleiner ist als die
aktuelle, aktualisiere die Distanz und setze den aktuellen Knoten als
Vorgänger. Dieser Schritt wird auch als Update bezeichnet und ist die
zentrale Idee von Dijkstra.
- Wähle einen Knoten mit minimaler temporärer Distanz als aktiv. Markiere
seine Distanz als permanent.
- Wiederhole 4-7, bis es keinen Knoten mit permanenter Distanz gibt, dessen
Nachbarn noch temporäre Distanzen haben.
Funktionsweise:
The idea of the
algorithm is to, beginning from a starting point, continiously calculate the
smallest distance and to exclude longer distances when making an update. It
consists of the following steps:
- Initialization of all nodes with distance "infinit", the one of the
starting node with 0.
- Marking of the distance of the starting node as permanent, all other
distances as temporarily.
- Setting of starting node as active.
- Calculation of the temporary distances of all neighbour nodes of the
active node by summing up its distance with the weights of the edges.
- If such a calculated distance of a node is smaller as the current one,
update the distance and set the current node as antecessor. This step is
also called update and is Dijkstra's central idea.
- Setting of the node with the minimal temporary distance as active. Mark
its distance as permanent.
- Repeating of steps 4 to 7 until there aren't any nodes left with a
permanent distance, which neighbours still have temporary distances.
1: |
function Dijkstra(Graph, source):
|
2: |
for each vertex v in Graph:
|
// Initialization |
3: |
dist[v] := infinity |
// initial distance from source to vertex v is set to infinite |
4: |
previous[v] := undefined |
// Previous node in optimal path from source |
5: |
dist[source] := 0 |
// Distance from source to source |
6: |
Q := the set of all nodes in Graph |
// all nodes in the graph are unoptimized - thus are in Q |
7: |
while Q is not empty:
|
// main loop |
8: |
u := node in Q with smallest dist[
]
|
9: |
remove u from Q |
10: |
for each neighbor v of u:
|
// where v has not yet been removed from Q. |
11: |
alt := dist[u] + dist_between(u, v) |
12: |
if alt < dist[v]
|
// Relax (u,v) |
13: |
dist[v] := alt |
14: |
previous[v] := u |
15: |
return previous[ ]
|