python - 修改加权图

Question

我编写了一段代码来遍历无向非加权图。现在我希望这段代码适用于加权图，其中权重将确定节点之间的距离，而我的代码将给出起始节点和结束节点之间的最短路径。我无法获取代码的逻辑。有人可以帮我吗？

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')

Answer 1

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)