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 ≤ in - 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 következő ábrán egy gráfot mutatunk. Határozzuk meg azt, hogy milyen súlyú utakon tudunk eljutni az u0 csúcspontból a gráf többi csúcspontjába!

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.