10.8 A legrövidebb út problémája
Adott egy súlyozott gráf, (vasút hálózat). Határozzuk meg a legrövidebb utat a gráf - előre adott - két csúcspontja (városa) között. (Ebben a környezetben az út hosszán a út által reprezentált részgráf éleihez rendelt súlyok összegét értjük.)
A probléma megoldására Dijkstra adott egy szép algoritmust 1959-ben.
Tegyük fel, hogy az u0 és a v0 csúcsok közötti út
hosszát akarjuk meghatározni. Az algoritmus egy fokozatosan növekvő Si halmazt
készít, ahol 0 ≤ i ≤ n - 1, és . Minden
lépésben egy címkét rendelünk a csúcspontokhoz:
úgy, hogy a
csúcshoz tartozó l(v) címke a v csúcs távolságát adja
meg az u0 csúcstól az <S>
indukált részgráfban.
12. ábra A Dijkstra algoritmus a legrövidebb út problémájának megoldására
A Dijkstra algoritmus egyes lépéseihez tartozó értékeket mutatja a következő ábra. A besatírozott értékek mutatják az adott csúcshoz tartozó legrövidebb út összértékét.