python - 如何应用动态规划来计算图中的最短路径？

Question

我正在尝试使用 Python 中的动态编程计算最短路径。我将所有数据正确存储为图的加权段（道路）和节点（城市），所以这不是问题，因为我能够实现经典算法（BFS，DFS ...），情况是我没有知道如何应用动态规划来解决这个问题。我只知道从A到B，我必须将问题划分为子问题，但我不知道如何创建一个有效的算法，我的意思是算法应该遵循的步骤以及我应该如何划分问题成小问题。

谢谢你的帮助！

Answer 1

如建议的那样，您可以查看 Bellman Ford 算法。如果你想自己实现它，维基百科提供了一个很好的伪代码：https ://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

否则，您可以使用 Python 中的 networkx 包（https://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus#Software）。

import networkx as nx
G = nx.Graph()
e = [('a', 'b', 3), ('b', 'c', 9), ('a', 'c', 5), ('c', 'd', 12)]
G.add_weighted_edges_from(e)
print(nx.bellman_ford_path(G, 'a', 'd'))
print(nx.bellman_ford_path_length(G, 'a', 'd'))