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.

The content of the graph configuration file which is saved as

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

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

cheers!

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!

## No comments:

## Post a Comment