### Dijkstra's Shortest Path Algorithm and Its Python Code

This algorithm finds the length of the shortest path from vertex a to vertex z in a connected, weighted graph. The weight of edge (i , j) is w(i , j) > 0 and the label of vertex x is L(x). At termination, L(z) is the length of the shortest path from a to z.

Input: A connected, weighted graph in which all weights are positive; vertices a and z
Output: L(z), the length of the shortest path from a to z
1. Dijkstra(w,a,z,l)
2.        L(a)=0
3.         for all vertices x ≠ a
4.             L(x)  =
5.        T = set of all vertices
6.       // T is the set of vertices whose shortest distance from a has
7.      // not been found
8.       while(z ∈ T) {
9.            choose v ∈ T with minimum L(v)
10.            T = T -{v}
11.            for each x ∈ T adjacent to v
12.                 L(x) = min{ L(x) , L(v) + w(v,x)}
13.           }
14. }

NOTE: Algorithm From Discrete Mathematics By Richard Johnsonbaugh
PYTHON CODE:
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35``` ```def dijkstra(graph, fromVertex, toVertex): notCalculated = {vertex: [float('inf'), None] for vertex in graph} notCalculated[fromVertex] = 0; calculated = {} while toVertex in notCalculated: v = min(notCalculated, key = notCalculated.get) calculated[v] = notCalculated.pop(v) for x in notCalculated: if notCalculated[x] > calculated[v] + graph[v][x]: notCalculated[x] = [calculated[v] + graph[v][x], v] shortDist = calculated[v] path = [] while v != None: path += v v = calculated[v] return shortDist, list(reversed(path)) vertex = [str(input("Enter node name: ")) for _ in range(int(input("Enter number of node:")))] #graph = {rowVertex: {colVertex: float(input("Enter weight of edge (" + rowVertex + ", " + colVertex + "): ")) for colVertex in vertex} for rowVertex in vertex} graph = {} for rowVertex in vertex: graph[rowVertex] = {} for colVertex in vertex: graph[rowVertex][colVertex] = graph[colVertex][rowVertex] = float(input("Enter weight of edge (" + rowVertex + ", " + colVertex + "): ")) if colVertex == rowVertex: break result = dijkstra(graph, str(input("Enter start vertex: ")), str(input("Enter end vertex: "))) print("Shortest Path distance is: ", result, "\nThe path is: ", result) ```