### 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*

*Dijkstra(w,a,z,l)**L(a)=0**for all vertices x ≠ a**L(x) =***∞***T = set of all vertices**// T is the set of vertices whose shortest distance from a has**// not been found**while(z ∈ T) {**choose v ∈ T with minimum L(v)**T = T -{v}**for each x ∈ T adjacent to v**L(x) = min{ L(x) , L(v) + w(v,x)}**}**}*

__NOTE: Algorithm From Discrete Mathematics By Richard Johnsonbaugh__

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] = 0; calculated = {} while toVertex in notCalculated: v = min(notCalculated, key = notCalculated.get) calculated[v] = notCalculated.pop(v) for x in notCalculated: if notCalculated[x][0] > calculated[v][0] + graph[v][x]: notCalculated[x] = [calculated[v][0] + graph[v][x], v] shortDist = calculated[v][0] path = [] while v != None: path += v v = calculated[v][1] 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[0], "\nThe path is: ", result[1]) |

## Comments

## Post a Comment

Need Help? Make a comment below & we'll help you out... :)