470,849 Members | 1,206 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 13860 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.
23.         self.vertices.append(vertice)
24.         self.order=len(self.vertices)
25.         self.makematrix()
26.
28.         self.vertices+=vertices
29.         self.order=len(self.vertices)
30.         self.makematrix()
32.         self.edges.append(edge)
33.         self.size=len(self.edges)
34.         self.makematrix()
35.
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:
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

 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 ryjfgjl | last post: by reply views Thread by AlexandraMT | last post: by 1 post views Thread by DANILIN | last post: by 1 post views Thread by MarkDoronin | last post: by reply views Thread by sjain6 | last post: by reply views Thread by milkinvl | last post: by reply views Thread by shivajikobardan | last post: by reply views Thread by gglobus | last post: by reply views Thread by zachatmarco | last post: by