Bytes - insights http://bytes.com en Sat, 21 Nov 2009 01:31:59 GMT vBulletin 60 http://bytes.com/images/misc/rss.jpg Bytes - insights http://bytes.com <![CDATA[Why general organisations don't use python??]]> http://bytes.com/topic/python/insights/877346-why-general-organisations-dont-use-python Fri, 20 Nov 2009 05:35:52 GMT http://programminglanguagefaqs.blogspot.com/2009/11/why-organizations-dont-use-python.html http://programminglanguagefaqs.blogs...se-python.html ]]> insights coders http://bytes.com/topic/python/insights/877346-why-general-organisations-dont-use-python <![CDATA[Dijkstra's Algorithm for finding the shortest route]]> http://bytes.com/topic/python/insights/877227-dijkstras-algorithm-finding-shortest-route Wed, 18 Nov 2009 09:16:55 GMT 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. ]]> insights Glenton http://bytes.com/topic/python/insights/877227-dijkstras-algorithm-finding-shortest-route