Til forskjell på Minimale spenntrær, som tar for seg uretta grafer, tar korteste vei problemer for seg rettede grafer. Vi bryr oss også om startnoden.
Har Optimal Delstruktur.
Engelsk: Single source shortest paths
Problemet:
Enkel sti
Algoritmer
Bellman-Ford sjekker negative sykler, og bruker RELAX ganger Dag-Shortest-Paths ser kun på asykliske grafer.
Bellman-Ford Dag-Shortest-Paths Dijkstras algoritme