Как применить динамическое программирование для вычисления кратчайшего пути в графе?

Question

Я пытаюсь вычислить кратчайший путь, используя динамическое программирование на Python.У меня все данные правильно хранятся в виде взвешенных сегментов (дороги) и узлов (городов) графа, так что это не проблема, так как я смог реализовать классические алгоритмы (BFS, DFS ...), дело в том, что я незнать, как применить динамическое программирование, чтобы решить эту проблему.Я только знаю, что для перехода от А к В я должен разделить проблему на подзадачи, но я не знаю, как создать работающий алгоритм, я имею в виду шаги, которым должен следовать алгоритм, а также то, как я должен делить проблемыв небольшие проблемы.

Спасибо за вашу помощь!

Answer 1

как предложено, вы можете посмотреть на алгоритм Беллмана Форда.Если вы хотите реализовать это самостоятельно, в Википедии есть хороший псевдокод: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

В противном случае вы можете использовать пакет networkx в Python (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'))