## Friday, February 24, 2012

### 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")
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])))
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!