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:

1. Initialisierung aller Knoten mit der Distanz "unendlich", die des Startknotens mit 0.
2. Markierung der Distanz des Startknotens als permanent, alle anderen Distanzen als temporär.
3. Setze Startknoten als aktiv.
4. Berechne die temporären Distanzen aller Nachbarknoten des aktiven Knotens durch Addition von dessen Distanz mit den Kantengewichten.
5. 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.
6. Wähle einen Knoten mit minimaler temporärer Distanz als aktiv. Markiere seine Distanz als permanent.
7. 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:

1. Initialization of all nodes with distance "infinit", the one of the starting node with 0.
2. Marking of the distance of the starting node as permanent, all other distances as temporarily.
3. Setting of starting node as active.
4. Calculation of the temporary distances of all neighbour nodes of the active node by summing up its distance with the weights of the edges.
5. 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.
6. Setting of the node with the minimal temporary distance as active. Mark its distance as permanent.
7. 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[ ]