主页 / 问题 / 1448228
Accepted
Nymos
Asked:2022-09-13 21:51:40 +0000 UTC2022-09-13 21:51:40 +0000 UTC

是否有可能在 Python 中解决这个问题？

  • 772

大家好，我有一个问题。老师说这个问题用Python是解决不了的。这是任务：

确定 B 点和 C 点之间最短路径的长度。您只能沿着道路移动，其长度如表中所示。

在此处输入图像描述

是否可以在 Python 中完成此任务？如果是这样，您能否放弃解决方案并向我解释您是如何做到的。

python

0 个回答

  1. Best Answer

    我为你做这个任务只是因为它对我刷新我对 NetworkX的知识很有用，所以我自己根据它的文档和 SO 上的其他答案几乎从头开始编写它：

    import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from((('A','B',3),('A','C',7),('A','F',2)))
G.add_weighted_edges_from((('C','D',3),('C','E',1)))
G.add_weighted_edges_from((('D','E',1),('D','F',2)))
pos = nx.spring_layout(G)
nx.draw_networkx(G,pos)
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)
print(nx.dijkstra_path(g, 'B', 'C'))
print(nx.dijkstra_path_length(g, 'B', 'C'))

    结论：

    ['B', 'A', 'F', 'D', 'E', 'C']
9

    在此处输入图像描述

    好吧，从图片来看，一切都是正确的。短路径的B->A->C权重为 10，Dijkstra 算法找到的长路径的权重为 9。

    如果您根本不需要任何库，那么您已经靠自己走得更远了。理论上，Dijkstra 的算法并不难实现。

    • 3

相关问题