Diskussion:Dijkstras algoritm
Grafen måste väl inte vara riktad? Vigfus 18 augusti 2006 kl. 15.50 (CEST)
- Nej, jag kan inte finna något som tyder på det, vare sig intuitivt eller i Dijkstras uppsats.[1] Han skriver dock i en fotnot att "processen kan också tillämpas i fall där en grens längd beror på i vilken riktning den följs". Förmodligen är det detta som auktoritativa källor som Cormen et al har tagit fasta på när de beskriver algoritmen som en metod att finna den kortaste vägen från en given utgångspunkt i en viktad och riktad graf.
- I princip är alla grafer riktade; en graf som inte är riktad kan ses som en riktad graf där det för varje kant (u, v) finns en motsvarande kant (v, u) så att δ(u, v) = δ(v, u). För dessa finns det dock effektivare lösningar, till exempel Mikkel Thorups algoritm (O(V + E)).