By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,218 Members | 1,255 Online
Bytes IT Community

Home Questions Articles Browse Topics Latest Top Members FAQ

home > topics > python > insights > dijkstra's algorithm for finding the shortest route
Submit an Article
Got Smarts?
Share your bits of IT knowledge by writing an article on Bytes.

Dijkstra's Algorithm for finding the shortest route

Expert 100+
P: 391
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[0]][edge[1]]=edge[2]
  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
Share this Article
Share on Google+
1 Comment
Expert 100+
P: 391
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[2])
  46.             eo.insert(n,e[2])
  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[0]][edge[1]]=edge[2]
  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[0],e[1])[0]==inf:
  102.                 T.addedge(e)
  103.                 T.addedge([e[1],e[0],e[2]])
  104.             if T.order-1==T.size/2:break
  105.         return T
  106.     def weight(self):
  107.         return sum([e[2] 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

Article Stats

  • viewed: 12375
  • comments: 1
  • date written:Nov 18 '09
BYTES.COM © 2020 About Bytes | Advertise on Bytes | Privacy Policy | Manage Cookies
Sitemap | Python Answers Sitemap | Python Insights Sitemap

Follow us to get the Latest Bytes Updates