graphs.dijkstra

pseudo-code

DIJKSTRA(graph G, start vertex s, destination vertex d):

//all nodes initially unexplored

1 - let H = min heap data structure, initialized with 0 and s [here 0 indicates

the distance from start vertex s]

2 - while H is non-empty: 3 - remove the first node and cost of H, call it U and cost 4 - if U has been previously explored: 5 - go to the while loop, line 2 //Once a node is explored there is no need

to make it again

6 - mark U as explored 7 - if U is d: 8 - return cost // total cost from start to destination vertex 9 - for each edge(U, V): c=cost of edge(U,V) // for V in graph[U] 10 - if V explored: 11 - go to next V in line 9 12 - total_cost = cost + c 13 - add (total_cost,V) to H

You can think at cost as a distance where Dijkstra finds the shortest distance between vertices s and v in a graph G. The use of a min heap as H guarantees that if a vertex has already been explored there will be no other path with shortest distance, that happens because heapq.heappop will always return the next vertex with the shortest distance, considering that the heap stores not only the distance between previous vertex and current vertex but the entire distance between each vertex that makes up the path from start vertex to target vertex.

Attributes

G	Layout of G2:
G2	Layout of G3:
G3
short_distance
short_distance
short_distance

Functions

dijkstra(graph, start, end)

Return the cost of the shortest path between vertices start and end.

Module Contents

graphs.dijkstra.dijkstra(graph, start, end)

Return the cost of the shortest path between vertices start and end.

>>> dijkstra(G, "E", "C")
6
>>> dijkstra(G2, "E", "F")
3
>>> dijkstra(G3, "E", "F")
3

graphs.dijkstra.G

Layout of G2:

E – 1 –> B – 1 –> C – 1 –> D – 1 –> F

/

||

—————– 3 ——————–

graphs.dijkstra.G2

Layout of G3:

E – 1 –> B – 1 –> C – 1 –> D – 1 –> F

/

||

——– 2 ———> G ——- 1 ——

graphs.dijkstra.G3

graphs.dijkstra.short_distance

graphs.dijkstra.short_distance

graphs.dijkstra.short_distance