How to apply dynamic programming to compute shortest path in graph?

Question

I'm trying to compute the shortest path using dynamic programming in Python. I have all data properly stored as weighted segments (road) and nodes (cities) of a graph so this is not a problem as I was able to implement classical algorithms (BFS,DFS...), the case is that I do not know how to apply dynamic programming to solve this. I only know that for going from A to B, I have to divide the problem in subproblems but I do not know how to create an algorithm that works, I mean the steps that the algorithm should follow as well as how I should divide the problems into small problems.

Thanks for your help!

Answer 1

as suggested, you can look at the Bellman Ford algorithm. If you want to implement it yourself, wikipedia provides a nice pseudo code: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

Otherwise, you could use the networkx package in 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'))