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

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

关于python - 修改加权图,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/57810767/

10-12 18:31