我已经编写了遍历无向非加权图的代码。现在,我希望此代码适用于加权图,其中权重将确定节点之间的距离,而我的代码将给出起始节点和结束节点之间的最短路径。我无法获得代码的逻辑。有人可以帮帮我吗。
graph = {'A': ['B', 'C', 'E'],
'B': ['A','D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'E': ['A', 'B','D'],
'F': ['C'],
'G': ['C']}
def undirected_graph(graph,start,stop):
visited = []
queue = [start]
if start == stop:
print("Woah we ended before even starting!")
else:
while queue:
path = queue.pop(0)
node = path[-1]
if node not in visited:
visited.append(node)
neighbours = graph[node]
for neighbour in neighbours:
new_list = list(path)
new_list.append(neighbour)
queue.append(new_list)
if neighbour == stop:
print("We reached the end")
return new_list
undirected_graph(graph,'A','G')
最佳答案
networkx
模块允许您创建图并找到最短路径(Dijkstra方法)。它与Anaconda发行版一起安装,否则请使用pip install
。
这是一个例子:
import networkx as nx
import pandas as pd
data = pd.read_excel('network.xlsx') # Some Graph
data
输出:
Origin Destination Distance
0 A B 10
1 A C 20
2 A D 15
3 B D 10
4 B E 5
5 C F 20
6 C G 20
7 C D 15
8 D G 20
df = nx.from_pandas_edgelist(data, source='Origin', target='Destination', edge_attr=True)
nx.dijkstra_path(df, source='E', target='F', weight='Distance')
输出:
['E', 'B', 'D', 'C', 'F']
networkx
模块提供更多信息:https://networkx.github.io/documentation/stable/tutorial.html例如,您可以绘制网络:
nx.draw_networkx(df, with_labels=True)
关于python - 修改加权图,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/57810767/