在图形上查找路径。它可以帮助我访问所有点并计算距离

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')。文档是here