468,554 Members | 1,722 Online

# Dijkstra's Algorithm for finding the shortest route 391 Expert 256MB
Hi All

Here is a very simple little class for finding a shortest route on a network, following Dijkstra's Algorithm:

Expand|Select|Wrap|Line Numbers
1. #!/usr/bin/env python
2. #This is meant to solve a maze with Dijkstra's algorithm
3. from numpy import inf
4. from copy import copy
5.
6. class Graph(object):
7.     """A graph object that has a set of singly connected,weighted,
8.     directed edges and a set of ordered pairs. Can be changed into
9.     a connection matrix. Vertices are [0,1,...,n], and edges are
10.     [[1,2,3],[2,1,1],...] where the first means 1 connected to 2
11.     with weight 3, and the second means 2 connected to 1 with
12.     weight 1."""
13.
14.     def __init__(self,vertices,edges):
15.         self.vertices=vertices
16.         self.size=len(self.vertices)
17.         self.edges=edges
18.         self.makematrix()
19.
20.     def makematrix(self):
21.         "creates connection matrix"
22.         self.matrix=[]
23.         for i in range(self.size):
24.             self.matrix.append([])
25.             for j in range(self.size):
26.                 self.matrix[i].append(inf)
27.         for edge in self.edges:
28.             self.matrix[edge][edge]=edge
29.
30.     def dijkstra(self,startvertex,endvertex):
31.         #set distances
32.         self.distance=[]
33.         self.route=[]
34.         for i in range(self.size):
35.             self.distance.append(inf)
36.             self.route.append([])
37.         self.distance[startvertex]=0
38.         self.route[startvertex]=[startvertex,]
39.         #set visited
40.         self.visited=[]
41.         self.current=startvertex
42.         while self.current<>None:
43.             self.checkunvisited()
44.             if endvertex in self.visited: break
45.         return self.distance[endvertex],self.route[endvertex]
46.
47.     def checkunvisited(self):
48.         basedist=self.distance[self.current]
49.         self.visited.append(self.current)
50.         for vertex,dist in enumerate(self.matrix[self.current]):
51.             if vertex in self.visited: continue #only check unvisited
52.             #set the distance to the new distance
53.             if basedist+dist<self.distance[vertex]:
54.                 self.distance[vertex]=basedist+dist
55.                 self.route[vertex]=copy(self.route[self.current])
56.                 self.route[vertex].append(vertex)
57.         #set next current node as one with smallest distance from initial
58.         self.current=None
59.         mindist=inf
60.         for vertex,dist in enumerate(self.distance):
61.             if vertex in self.visited: continue
62.             if dist<mindist:
63.                 mindist=dist
64.                 self.current=vertex
65.
66.
67.
68. def main():
69.     #This solves the maze in the wikipedia article on Dijkstra's algorithm
70.     #Note that the vertices are numbered modulo 6, so 6 is called 0 here
71.     V=range(6)
72.     E=[[1,2,7],[1,3,9],[1,0,14],[2,1,7],[2,3,10],[2,4,15],[3,1,9],[3,2,10],
73.     [3,4,11],[3,0,2],[4,2,15],[4,3,11],[4,5,6],[5,4,6],[5,0,9],[0,1,14],
74.     [0,3,2],[0,5,9]]
75.     m=Graph(V,E)
76.     print "size of graph is", m.size
77.
78.     print "distance and best route is", m.dijkstra(1,5)
79.
80.
81.
82. if __name__=="__main__": main()
83.
The main here is just an example, implementing the network shown in the wikipedia article. To use it, you simply need to get your network arranged into a list of vertices (0,1,...,n-1), and your edges into a list of coordinates of the form [a,b,d], where the edge is from a to b with weight d. If you want undirected, you simply need to add [b,a,d]. If you want unweighted you need to just set d=1.

I've been planning the design of some mazes for the local science centre, which is why I've got this! Any improvements/comments are welcome.
Nov 18 '09 #1
1 13215 Glenton
391 Expert 256MB
Hi

So here I've beefed up the Graph class a little bit.
- The main addition is the implementation of Kruskal's algorithm for finding minimum spanning trees. The neat part is that it uses Dijkstra's algorithm to determine whether two points are connected (at least I found it neat).
- Other improvements are the ability to add vertices and edges to a graph on the fly, and to input a graph by its matrix, rather than by its vertices and edges sets.

Expand|Select|Wrap|Line Numbers
1. #!/usr/bin/env python
2. #This is meant to solve a maze with Dijkstra's algorithm
3. from numpy import inf
4. from copy import copy
5. from bisect import bisect_left
6.
7. class Graph(object):
8.     """A graph object that has a set of singly connected,weighted,
9.     directed edges and a set of ordered pairs. Can be changed into
10.     a connection matrix. Vertices are [0,1,...,n], and edges are
11.     [[1,2,3],[2,1,1],...] where the first means 1 connected to 2
12.     with weight 3, and the second means 2 connected to 1 with
13.     weight 1."""
14.
15.     def __init__(self,vertices=[],edges=[]):
16.         self.vertices=vertices
17.         self.order=len(self.vertices)
18.         self.edges=edges
19.         self.size=len(edges)
20.         self.makematrix()
21.
22.     def addvertice(self,vertice):
23.         self.vertices.append(vertice)
24.         self.order=len(self.vertices)
25.         self.makematrix()
26.
27.     def addvertices(self,vertices):
28.         self.vertices+=vertices
29.         self.order=len(self.vertices)
30.         self.makematrix()
31.     def addedge(self,edge):
32.         self.edges.append(edge)
33.         self.size=len(self.edges)
34.         self.makematrix()
35.
36.     def addedges(self,edges):
37.         self.edges+=edges
38.         self.size=len(self.edges)
39.         self.makematrix()
40.
41.     def orderedges(self):
42.         E=[]
43.         eo=[]
44.         for e in self.edges:
45.             n=bisect_left(eo,e)
46.             eo.insert(n,e)
47.             E.insert(n,e)
48.         self.edges=E
49.     def makematrix(self):
50.         "creates connection matrix"
51.         self.matrix=[]
52.         for i in range(self.order):
53.             self.matrix.append([])
54.             for j in range(self.order):
55.                 self.matrix[i].append(inf)
56.         for edge in self.edges:
57.             self.matrix[edge][edge]=edge
58.
59.     def dijkstra(self,startvertex,endvertex):
60.         #set distances
61.         self.distance=[]
62.         self.route=[]
63.         for i in range(self.order):
64.             self.distance.append(inf)
65.             self.route.append([])
66.         self.distance[startvertex]=0
67.         self.route[startvertex]=[startvertex,]
68.         #set visited
69.         self.visited=[]
70.         self.current=startvertex
71.         while self.current<>None:
72.             self.checkunvisited()
73.             if endvertex in self.visited: break
74.         return self.distance[endvertex],self.route[endvertex]
75.
76.     def checkunvisited(self):
77.         basedist=self.distance[self.current]
78.         self.visited.append(self.current)
79.         for vertex,dist in enumerate(self.matrix[self.current]):
80.             if vertex in self.visited: continue #only check unvisited
81.             #set the distance to the new distance
82.             if basedist+dist<self.distance[vertex]:
83.                 self.distance[vertex]=basedist+dist
84.                 self.route[vertex]=copy(self.route[self.current])
85.                 self.route[vertex].append(vertex)
86.         #set next current node as one with smallest distance from initial
87.         self.current=None
88.         mindist=inf
89.         for vertex,dist in enumerate(self.distance):
90.             if vertex in self.visited: continue
91.             if dist<mindist:
92.                 mindist=dist
93.                 self.current=vertex
94.
95.
96.     def kruskal(self):
97.         self.orderedges()
98.         E=self.edges
99.         T=Graph(self.vertices,[])
100.         for e in E:
101.             if T.dijkstra(e,e)==inf:
102.                 T.addedge(e)
103.                 T.addedge([e,e,e])
104.             if T.order-1==T.size/2:break
105.         return T
106.     def weight(self):
107.         return sum([e for e in self.edges])
108.     def setmatrix(self,matrix):
109.         E=[]
110.         V=range(len(matrix))
111.         for i,row in enumerate(matrix):
112.             for j,col in enumerate(row):
113.                 if col<inf:
114.                     E.append([i,j,col])
115.         self.__init__(V,E)
116.
117. def main():
118.     #This solves the maze in the wikipedia article on Dijkstra's algorithm
119.     #Note that the vertices are numbered modulo 6, so 6 is called 0 here
120.     V=range(6)
121.     E=[[1,2,7],[1,3,9],[1,0,14],[2,1,7],[2,3,10],[2,4,15],[3,1,9],[3,2,10],
122.     [3,4,11],[3,0,2],[4,2,15],[4,3,11],[5,4,6],[5,0,9],[0,1,14],
123.     [0,3,2],[0,5,9],[4,5,6]]
124.     m=Graph(V,E)
125.     print "order of graph is", m.order
126.     print "distance and best route is", m.dijkstra(1,5)
127.     print "edges", m.edges
128.     m.orderedges()
129.     print "ordered edges", m.edges
130.     T=m.kruskal()
131.     print "Minimum spanning tree:"
132.     print "Vertices",T.vertices
133.     print "Edges",T.edges
134.     print "Matrix:"
135.     print T.matrix
136.     print "Weight",T.weight()/2
137.     M=m.matrix
138.     m2=Graph()
139.     m2.setmatrix(M)
140.
141.     M=[[inf,16,12,21,inf,inf,inf],
142.         [16,inf,inf,17,20,inf,inf],
143.         [12,inf,inf,28,inf,31,inf],
144.         [21,17,28,inf,18,19,23],
145.         [inf,20,inf,18,inf,inf,11],
146.         [inf,inf,31,19,inf,inf,27],
147.         [inf,inf,inf,23,11,27,inf]]
148.     G=Graph()
149.     G.setmatrix(M)
150.     T=G.kruskal()
151.     print "Savings is",G.weight()/2-T.weight()/2
152.
153. if __name__=="__main__": main()
154.
Jan 12 '10 #2

### Post your reply

Sign in to post your reply or Sign up for a free account.

### Similar topics

 6 posts views Thread by ThanhVu Nguyen | last post: by 3 posts views Thread by A_StClaire_ | last post: by 3 posts views Thread by Ook | last post: by 1 post views Thread by arlef | last post: by 8 posts views Thread by abhradwip | last post: by 2 posts views Thread by Gurpreet Singh | last post: by 4 posts views Thread by prometheuzz | last post: by 1 post views Thread by Ganon11 | last post: by 2 posts views Thread by shashankbs | last post: by reply views Thread by NPC403 | last post: by reply views Thread by slotstar | last post: by 7 posts views Thread by isladogs | last post: by reply views Thread by captainhaddock | last post: by reply views Thread by yuyenews | last post: by 3 posts views Thread by laxmi96 | last post: by 7 posts views Thread by Barbara1999 | last post: by 1 post views Thread by UniDue | last post: by reply views Thread by PrototypeChain | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.