Wednesday, July 12, 2017

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] = 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])



No comments:
Write comments

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