Dijkstra's Shortest Path Algorithm implemented in Python

For an assignment work I had to implement the shortest path algorithm and the longest path algorithm recently. Since the implementation language was our choice I used Python to implement it since I was thinking to learn Python for a long time. I took this assignment as an opportunity to learn Python.

Here I write down the source codes of the dijkstra's shortest path algorithm I implemented in Python. This may not be the best way to code it. But this is what my poor Python skills returned. However now I have a considerable exposure in the language and therefore hope I will use it in better ways in the future.

The input graph to the program is given as a separate configuration file which also I have shown.

shortest_path.py file

1:  #!/usr/bin/python  
2:  import string  
3:  import time  
4:    
5:  # represents a vertex in the graph  
6:  class Vertex:  
7:       def __init__(self, name):  
8:            self.name = name         # name of the vertex  
9:            self.dist = 1000         # distance to this vertex from start vertex  
10:            self.prev = None        # previous vertex to this vertex  
11:            self.flag = 0           # access flag  
12:     
13:     
14:  # represents an edge in the graph  
15:  class Edge:  
16:       def __init__(self, u, v, length):  
17:            self.start = u  
18:            self.end = v  
19:            self.length = length  
20:    
21:    
22:  # read a text file and generate the graph according to declarations  
23:  def generateGraph(V, E):  
24:       file = open("graph_def", "r")  
25:       line = file.readline()  
26:       line = line[:-1]  
27:       while line:  
28:            taglist = string.split(line)  
29:            if taglist[0] == 'vertex':  
30:                 V.append(Vertex(taglist[1]))  
31:            elif taglist[0] == 'edge':  
32:                 E.append(Edge(taglist[1], taglist[2], string.atoi(taglist[3])))  
33:                 E.append(Edge(taglist[2], taglist[1], string.atoi(taglist[3])))  
34:            line = file.readline()  
35:            line = line[:-1]            
36:       file.close()  
37:    
38:    
39:  # returns the smallest vertex in V but not in S  
40:  def pickSmallestVertex(V):  
41:       minVertex = None  
42:       for vertex in V:  
43:            if vertex.flag == 0:  
44:                 minVertex = vertex  
45:                 break  
46:       if minVertex == None:  
47:            return minVertex  
48:       for vertex in V:  
49:            if vertex.flag == 0 and vertex.dist < minVertex.dist:  
50:                 minVertex = vertex  
51:       return minVertex  
52:    
53:    
54:  # returns the edges list of vertex u  
55:  def pickEdgesList(u, E):  
56:       uv = []  
57:       for edge in E:  
58:            if edge.start == u.name:  
59:                 uv.append(edge)  
60:       return uv  
61:    
62:    
63:  def findShortestPath(V, E, S, A):  
64:       # set A vertex distance to zero  
65:       for vertex in V:  
66:            if vertex.name == A:  
67:                 vertex.dist = 0  
68:    
69:       u = pickSmallestVertex(V)  
70:       while u != None:  
71:            u.flag = 1  
72:            uv = pickEdgesList(u, E)  
73:            v = None  
74:            for edge in uv:  
75:                 # take the vertex v  
76:                 for vertex in V:  
77:                      if vertex.name == edge.end:  
78:                           v = vertex  
79:                           break  
80:                 if v.dist > u.dist + edge.length:  
81:                       v.dist = u.dist + edge.length  
82:                      v.prev = u  
83:            u = pickSmallestVertex(V)  
84:    
85:    
86:  def printGraph(V, E):  
87:       print('vertices:')  
88:       for vertex in V:  
89:            previous = vertex.prev       
90:            if previous == None:  
91:                 print(vertex.name, vertex.dist, previous)  
92:            else:  
93:                 print(vertex.name, vertex.dist, previous.name)  
94:       print('edges:')  
95:       for edge in E:       
96:            print(edge.start, edge.end, edge.length)  
97:    
98:    
99:  def main():  
100:       print('Starting Dijkstra\'s Algorithm...')       
101:       t1 = time.time()  
102:       # graph elements  
103:       V = []  
104:       E = []  
105:       S = []  
106:       generateGraph(V, E)       
107:       #printGraph(V, E)  
108:       findShortestPath(V, E, S, 'a')  
109:       #printGraph(V, E)  
110:       print 'dummy '  
111:       t2 = time.time()  
112:       print t2-t1  
113:    
114:    
115:  main()  
116:    

The content of the graph configuration file which is saved as graph_def is as follows.

1:  vertex a  
2:  vertex b  
3:  vertex c  
4:  vertex d  
5:  ------------  
6:  edge a b 1  
7:  edge a c 1  
8:  edge a d 1  
9:  edge b c 1  
10:  edge b d 1  
11:  edge c d 1  

You can run this program on a Linux machined by typing the following line on the terminal,

python shortest_path.py

The longest path program implementation will be given as a separate post.

cheers!