python - 修改加权图

问题描述

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

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

标签： pythonshortest-pathbreadth-first-searchweighted-graph

该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 - 修改加权图

问题描述

解决方案

推荐阅读