- Finds the shortest (lowest-cost) path through a graph from the start node to all other nodes.
- This is the fastest, single-start, shortest path algorithm for directed and undirected networks with
unbounded, non-negative edge weights.
2. Description of the algorithm
- Set the current distance to 0 for your chosen beginning node and infinite for all other nodes.
- Mark your beggining node
- Set the current node C to the non-visited node with the shortest current distance.
- For each neighbor N of your current node C, add the current distance of C to the weight of the edge
connecting C-N. Set
it as the new current distance of N if it is less than the current distance of N.
- Mark the current node C as visited.
- If there are non-visited nodes, go to step 2.
3. Dijkstra Pseudocode
This pseudocode is referred to the Florian's lecture.
V = vertex, pq = priority queue, St = staring node, Sp = predecessor, C = unvisited vertex, W = weight
for each vertex V:
initialize V's visited mark to false
create minimum priority queue, pq, for vertices
pq.insert( [St: Sp, 0 ])
St = starting node, Sp = predeccessor node
while ( !pq.isEmpty() ):
[ C: Pred, Distance ] = pq.removeMinPathWeight()
if C is unvisited:
mark C as Visited, set predecessor to Previous Vertex, and cost to Distance in the graph
for each edge with weight W to unvisited successor(US) of C:
pq.insert( [ US: C, Distance + W ] )
4. The image that depicting the algorithm operates over
This image of a cute kitten is from a Medium post:An
Introduction to Dijkstra’s Algorithm: Theory and Python Implementation