PDF Version of this document Search Help Glossary

Lesson Navigation IconAccessibility (Network Analysis)

Unit Navigation IconWhat are networks

Unit Navigation IconStructural Properties of a Network

Unit Navigation IconDijkstra Algorithm

LO Navigation IconDijkstra Algorithm: Short terms and Pseudocode

LO Navigation IconDijkstra Algorithm: Step by Step

LO Navigation IconApplications, extensions, and alternatives

Unit Navigation IconTraveling Salesman Problem

Unit Navigation IconSummary

Unit Navigation IconGlossary

Unit Navigation IconBibliography

Unit Navigation IconIndex

Unit Navigation IconMetadata

GITTA/CartouCHe news:

Go to previous page Go to next page

Dijkstra Algorithm: Short terms and Pseudocode

Using the Dijkstra algorithm, it is possible to determine the shortest distance (or the least effort / lowest cost) between a start node and any other node in a graph. The idea of the algorithm is to continiously calculate the shortest distance beginning from a starting point, and to exclude longer distances when making an update. It consists of the following steps:

  1. Initialization of all nodes with distance "infinite"; initialization 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[ ]
Top Go to previous page Go to next page