在图形上查找路径.这可以通过访问所有点并计算距离来帮助我

Question

我找不到应该覆盖我所有顶点和边的路径。我们也可以再次访问Vertiex。

我能够找到从一个点到另一个点的路径，但这并不能涵盖所有点。

 import networkx as nx
 import matplotlib.pyplot as plt
 class Node:
     def addNode(self,graph,name,o_time,c_time):
         graph.add_node(name,open_time=o_time,close_time=c_time)
     def updateNode(self,graph,name,o_time,c_time):
         if name in graph:
             attrs = {name:{'open_time': o_time, 'close_time': c_time}}
             nx.set_node_attributes(graph, attrs)
 class Edge(Node):
     def addEdge(self,graph,edge1,edge2,weight):
         if edge1 not in graph:
             Node.addNode(self,graph,edge1,'None','None')
         if edge2 not in graph:
             Node.addNode(self,graph,edge2,'None','None')
         graph.add_edge(edge1,edge2,weight=weight)
 G = nx.Graph()
 d = Node()
 edge = Edge()
 d.addNode(G,'Ngurah Rai International Airport','8:00Am','8:00Pm')
 d.addNode(G,'Tanah Lot Temple','8:00Am','8:00Pm')
 d.addNode(G,'Mt Batur','9:00Am','9:00Pm')
 d.addNode(G,'Uluwatu Temple','10:00Am','10:00Pm')
 d.addNode(G,'Sacred Monkey Forest Sanctuary','10:00Am','10:00Pm')
 d.addNode(G,'Agung Rai Museum of Art','10:00Am','10:00Pm')
 d.addNode(G,'Tegallalang Rice Terrace','10:00Am','10:00Pm')
 d.addNode(G,'Waterbom Bali Indonesia','10:00Am','10:00Pm')
 d.addNode(G,'Ulun Danu Beratan Temple','10:00Am','10:00Pm')
 d.addNode(G,'Kuta Beach','10:00Am','10:00Pm')
 edge.addEdge(G,'Ngurah Rai International Airport','Kuta Beach',20)
 edge.addEdge(G,'Ngurah Rai International Airport','Uluwatu Temple',50)
 edge.addEdge(G,'Kuta Beach','Tanah Lot Temple',70)
 edge.addEdge(G,'Sacred Monkey Forest Sanctuary','Agung Rai Museum of Art',20)
 edge.addEdge(G,'Ngurah Rai International Airport','Agung Rai Museum of Art',100)
 edge.addEdge(G,'Agung Rai Museum of Art','Tegallalang Rice Terrace',60)
 edge.addEdge(G,'Sacred Monkey Forest Sanctuary','Tegallalang Rice Terrace',50)
 edge.addEdge(G,'Tegallalang Rice Terrace','Mt Batur',100)
 edge.addEdge(G,'Ngurah Rai International Airport','Waterbom Bali Indonesia',10)
 edge.addEdge(G,'Waterbom Bali Indonesia','Kuta Beach',10)
 edge.addEdge(G,'Tanah Lot Temple','Ulun Danu Beratan Temple',70)
 edge.addEdge(G,'Kuta Beach','Ulun Danu Beratan Temple',100)
 d.updateNode(G,'Los','10:00Am','10:00Pm')
 start = 'Ngurah Rai International Airport'
 for node in G.nodes():
     for path in nx.all_simple_paths(G, source=start, target=node):
         if(len(path) >= 5):
             print(path)
             print(str( nx.shortest_path_length(G, source=start, target=node, weight='weight') ) + 'Km')
 nx.draw(G,arrows=True,with_labels=True)
 plt.savefig("simple_path.png") # save as png
 plt.show()

电流输出为

'Ngurah Rai International Airport', 'Waterbom Bali Indonesia', 'Kuta Beach', 'Ulun Danu Beratan Temple', 'Tanah Lot Temple'
90Km
'Ngurah Rai International Airport', 'Agung Rai Museum of Art', 'Sacred Monkey Forest Sanctuary', 'Tegallalang Rice Terrace', 'Mt Batur'
260Km
'Ngurah Rai International Airport', 'Waterbom Bali Indonesia', 'Kuta Beach', 'Tanah Lot Temple', 'Ulun Danu Beratan Temple'
120Km

我期待输出为

'Ngurah Rai International Airport', 'Waterbom Bali Indonesia', 'Kuta Beach', 'Ulun Danu Beratan Temple', 'Tanah Lot Temple', 'Kuta Beach', 'Ngurah Rai International Airport', 'Ulluwalu Temple', 'Ngurah Rai International Airport', 'Agung Rai Museum of Art', 'Sacred Monkey Forest Sanctuary', 'Tegallalang Rice Terrace', 'Mt Batur'

Answer 1

你说你想要一条覆盖每条边的路径。 我假设您希望它恰好覆盖一次每个边缘。

那么你正在寻找一个欧拉回路。 (顺便说一下，当且仅当图连接并且所有节点都有偶数度时，它才存在(。

使用nx.eulerian_circuit(G, source=Ngurah Rai International Airport') . 文档在这里。