3 ms·

"Dijkstra's algorithm for shortest paths can be seen as DP" Really? Sure, if the graph is a dag, but then Dijkstra is overkill. Hmm. I'll have to think abou

• svat 8y ago
  Hmm, I wrote that from vague memory, and perhaps that's debatable! (There seem to be different communities that use “dynamic programming” slightly differently.) But my main point was: if one can look at the shortest-path problem and formulate something like distance(v) = min_{u->v} (distance(u) + edge_length(u, v)) then one probably has a handle on whatever it is that's hard about dynamic programming. Actually Wikipedia cites some references that consider Dijkstra's algorithm a case of DP: https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algorithm&oldid=876084651#Dynamic_programming_perspective https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algo... and the same text (Wikipedia doesn't care about “self-plagiarism”) is also on the DP page where Dijkstra's algorithm is given as the first example: https://en.wikipedia.org/w/index.php?title=Dynamic_programming&oldid=876525808#Dijkstra's_algorithm_for_the_shortest_path_problem https://en.wikipedia.org/w/index.php?title=Dynamic_programmi...