大家好,大家好
下面是一个非常简单的小类,用于查找网络上的最短路径,如下所示
狄克斯特拉算法
:
- #!/usr/bin/env python
- #This is meant to solve a maze with Dijkstra's algorithm
- from numpy import inf
- from copy import copy
-
- class Graph(object):
- """A graph object that has a set of singly connected,weighted,
- directed edges and a set of ordered pairs. Can be changed into
- a connection matrix. Vertices are [0,1,...,n], and edges are
- [[1,2,3],[2,1,1],...] where the first means 1 connected to 2
- with weight 3, and the second means 2 connected to 1 with
- weight 1."""
-
- def __init__(self,vertices,edges):
- self.vertices=vertices
- self.size=len(self.vertices)
- self.edges=edges
- self.makematrix()
-
- def makematrix(self):
- "creates connection matrix"
- self.matrix=[]
- for i in range(self.size):
- self.matrix.append([])
- for j in range(self.size):
- self.matrix[i].append(inf)
- for edge in self.edges:
- self.matrix[edge[0]][edge[1]]=edge[2]
-
- def dijkstra(self,startvertex,endvertex):
- #set distances
- self.distance=[]
- self.route=[]
- for i in range(self.size):
- self.distance.append(inf)
- self.route.append([])
- self.distance[startvertex]=0
- self.route[startvertex]=[startvertex,]
- #set visited
- self.visited=[]
- self.current=startvertex
- while self.current<>None:
- self.checkunvisited()
- if endvertex in self.visited: break
- return self.distance[endvertex],self.route[endvertex]
-
- def checkunvisited(self):
- basedist=self.distance[self.current]
- self.visited.append(self.current)
- for vertex,dist in enumerate(self.matrix[self.current]):
- if vertex in self.visited: continue #only check unvisited
- #set the distance to the new distance
- if basedist+dist<self.distance[vertex]:
- self.distance[vertex]=basedist+dist
- self.route[vertex]=copy(self.route[self.current])
- self.route[vertex].append(vertex)
- #set next current node as one with smallest distance from initial
- self.current=None
- mindist=inf
- for vertex,dist in enumerate(self.distance):
- if vertex in self.visited: continue
- if dist<mindist:
- mindist=dist
- self.current=vertex
-
-
-
- def main():
- #This solves the maze in the wikipedia article on Dijkstra's algorithm
- #Note that the vertices are numbered modulo 6, so 6 is called 0 here
- V=range(6)
- 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],
- [3,4,11],[3,0,2],[4,2,15],[4,3,11],[4,5,6],[5,4,6],[5,0,9],[0,1,14],
- [0,3,2],[0,5,9]]
- m=Graph(V,E)
- print "size of graph is", m.size
-
- print "distance and best route is", m.dijkstra(1,5)
-
-
-
- if __name__=="__main__": main()
-
这里的主要内容只是一个示例,实现维基百科文章中所示的网络。要使用它,您只需将您的网络排列成一个顶点列表(0,1,...,n-1),并将您的边排列成[a,b,d]形式的坐标列表,其中边是从a到b,权重为d。如果您想要无方向,您只需添加[b,a,d]。如果想取消加权,只需设置d=1即可。
我一直在计划为当地的科学中心设计一些迷宫,这就是为什么我得到了这个!欢迎您提出任何改进意见。
# 回答1
嗨
所以在这里,我对Graph类进行了一些改进。
-主要增加的是Kruskal寻找最小生成树的算法的实现。巧妙的部分是,它使用Dijkstra的算法来确定两个点是否相连(至少我发现它很整齐)。
-其他改进是能够动态地向图形添加顶点和边,以及通过其矩阵而不是通过其顶点和边集输入图形。
- #!/usr/bin/env python
- #This is meant to solve a maze with Dijkstra's algorithm
- from numpy import inf
- from copy import copy
- from bisect import bisect_left
-
- class Graph(object):
- """A graph object that has a set of singly connected,weighted,
- directed edges and a set of ordered pairs. Can be changed into
- a connection matrix. Vertices are [0,1,...,n], and edges are
- [[1,2,3],[2,1,1],...] where the first means 1 connected to 2
- with weight 3, and the second means 2 connected to 1 with
- weight 1."""
-
- def __init__(self,vertices=[],edges=[]):
- self.vertices=vertices
- self.order=len(self.vertices)
- self.edges=edges
- self.size=len(edges)
- self.makematrix()
-
- def addvertice(self,vertice):
- self.vertices.append(vertice)
- self.order=len(self.vertices)
- self.makematrix()
-
- def addvertices(self,vertices):
- self.vertices+=vertices
- self.order=len(self.vertices)
- self.makematrix()
- def addedge(self,edge):
- self.edges.append(edge)
- self.size=len(self.edges)
- self.makematrix()
-
- def addedges(self,edges):
- self.edges+=edges
- self.size=len(self.edges)
- self.makematrix()
-
- def orderedges(self):
- E=[]
- eo=[]
- for e in self.edges:
- n=bisect_left(eo,e[2])
- eo.insert(n,e[2])
- E.insert(n,e)
- self.edges=E
- def makematrix(self):
- "creates connection matrix"
- self.matrix=[]
- for i in range(self.order):
- self.matrix.append([])
- for j in range(self.order):
- self.matrix[i].append(inf)
- for edge in self.edges:
- self.matrix[edge[0]][edge[1]]=edge[2]
-
- def dijkstra(self,startvertex,endvertex):
- #set distances
- self.distance=[]
- self.route=[]
- for i in range(self.order):
- self.distance.append(inf)
- self.route.append([])
- self.distance[startvertex]=0
- self.route[startvertex]=[startvertex,]
- #set visited
- self.visited=[]
- self.current=startvertex
- while self.current<>None:
- self.checkunvisited()
- if endvertex in self.visited: break
- return self.distance[endvertex],self.route[endvertex]
-
- def checkunvisited(self):
- basedist=self.distance[self.current]
- self.visited.append(self.current)
- for vertex,dist in enumerate(self.matrix[self.current]):
- if vertex in self.visited: continue #only check unvisited
- #set the distance to the new distance
- if basedist+dist<self.distance[vertex]:
- self.distance[vertex]=basedist+dist
- self.route[vertex]=copy(self.route[self.current])
- self.route[vertex].append(vertex)
- #set next current node as one with smallest distance from initial
- self.current=None
- mindist=inf
- for vertex,dist in enumerate(self.distance):
- if vertex in self.visited: continue
- if dist<mindist:
- mindist=dist
- self.current=vertex
-
-
- def kruskal(self):
- self.orderedges()
- E=self.edges
- T=Graph(self.vertices,[])
- for e in E:
- if T.dijkstra(e[0],e[1])[0]==inf:
- T.addedge(e)
- T.addedge([e[1],e[0],e[2]])
- if T.order-1==T.size/2:break
- return T
- def weight(self):
- return sum([e[2] for e in self.edges])
- def setmatrix(self,matrix):
- E=[]
- V=range(len(matrix))
- for i,row in enumerate(matrix):
- for j,col in enumerate(row):
- if col<inf:
- E.append([i,j,col])
- self.__init__(V,E)
-
- def main():
- #This solves the maze in the wikipedia article on Dijkstra's algorithm
- #Note that the vertices are numbered modulo 6, so 6 is called 0 here
- V=range(6)
- 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],
- [3,4,11],[3,0,2],[4,2,15],[4,3,11],[5,4,6],[5,0,9],[0,1,14],
- [0,3,2],[0,5,9],[4,5,6]]
- m=Graph(V,E)
- print "order of graph is", m.order
- print "distance and best route is", m.dijkstra(1,5)
- print "edges", m.edges
- m.orderedges()
- print "ordered edges", m.edges
- T=m.kruskal()
- print "Minimum spanning tree:"
- print "Vertices",T.vertices
- print "Edges",T.edges
- print "Matrix:"
- print T.matrix
- print "Weight",T.weight()/2
- M=m.matrix
- m2=Graph()
- m2.setmatrix(M)
-
- M=[[inf,16,12,21,inf,inf,inf],
- [16,inf,inf,17,20,inf,inf],
- [12,inf,inf,28,inf,31,inf],
- [21,17,28,inf,18,19,23],
- [inf,20,inf,18,inf,inf,11],
- [inf,inf,31,19,inf,inf,27],
- [inf,inf,inf,23,11,27,inf]]
- G=Graph()
- G.setmatrix(M)
- T=G.kruskal()
- print "Savings is",G.weight()/2-T.weight()/2
-
- if __name__=="__main__": main()
-
评论已关闭