寻找最短路径的Dijkstra算法

大家好,大家好
下面是一个非常简单的小类,用于查找网络上的最短路径,如下所示
狄克斯特拉算法

选择 | 换行 | 行号
  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.  

这里的主要内容只是一个示例,实现维基百科文章中所示的网络。要使用它,您只需将您的网络排列成一个顶点列表(0,1,...,n-1),并将您的边排列成[a,b,d]形式的坐标列表,其中边是从a到b,权重为d。如果您想要无方向,您只需添加[b,a,d]。如果想取消加权,只需设置d=1即可。
我一直在计划为当地的科学中心设计一些迷宫,这就是为什么我得到了这个!欢迎您提出任何改进意见。

# 回答1



所以在这里,我对Graph类进行了一些改进。
-主要增加的是Kruskal寻找最小生成树的算法的实现。巧妙的部分是,它使用Dijkstra的算法来确定两个点是否相连(至少我发现它很整齐)。
-其他改进是能够动态地向图形添加顶点和边,以及通过其矩阵而不是通过其顶点和边集输入图形。

选择 | 换行 | 行号
  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.  

标签: python

评论已关闭