79787593

Date: 2025-10-10 17:46:33
Score: 0.5
Natty:
Report link

Dijkstra's finds the shortest path from x to y by calculating, and using, the shortest path to all nodes z, that are adjacent to y and closer to x than y is: it is the minimum of dist(z) + weight(z,y) for all such z.

An optimal substructure defines an ordering, and an ordering also defines an optimal substructure, so a great many algorithms, have an optimal substructure, e.g. summing the values in an array via partial sum of the elements before it, but are not traditionally classified as dynamic programming algorithms.

CLRS:
Shortest-paths algorithms typically rely on the property that a shortest path between two vertices contains other shortest paths within it. (The Edmonds-Karp maximum-flow algorithm in Chapter 26 also relies on this property.) This optimal substructure property is a hallmark of the applicability of both dynamic programming (Chapter 15) and the greedy method (Chapter 16). https://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/shortestPaths.pdf

Reasons:
  • Long answer (-0.5):
  • No code block (0.5):
  • Low reputation (0.5):
Posted by: Daniel Ford