Legrövidebb út keresése

- adott egy összefüggő G = (V,E) gráf és egy kitüntetett s pontja
- a legrövidebb út megkeresésére különböző eljárások vannak:

I.)    - ha az élek száma adja az út hosszát, azaz az élek nem súlyozottak, a szélességi keresést (BFS) kell alkalmazni

        - a szélességi bejárás lényege, hogy a kezdőpontból először elmegyünk annak összes szomszédjába, majd az első szomszéd összes olyan szomszédjába, ahol még nem jártunk

        - ha az összes szomszédot bejártuk, elmegyünk abba a pontba, ahol a legrégebben jártunk, és szomszédain folytatjuk a bejárást

        - mindezt addig folytatjuk, ameddig tudjuk

       - ha s és t  közti legrövidebb utat keressük, a kiválasztott t ponthoz meghatározzuk a q(t) = u₁ pontot; ha u₁ nem egyenlő s, akkor a q(u₁) = u₂ pontot, és így tovább, amíg u_k = s lesz, és akkor az s-ből t-be vezető legrövidebb út az (s = u_k, u_k-1, u_k-2, …, u₁,t) lesz

        - a bejárás lépésszáma (e+v)-vel arányos, utána még annyi lépés kell, amilyen hosszú a keresett út

II.)   - az élek különböző hosszúságú utakat modelleznek, azaz súlyozottak

        - ha bejárjuk a gráfot, az u pontra d(u) értéke azt fogja jelenteni, hogy az algoritmus során eddig talált, az s kezdőpontból u-ba vezető utak közül a legrövidebb hossza d(u)

        - a Dijkstra algoritmus akkor használható, ha minden él hossza nemnegatív

        - az algoritmus kulcslépése a következő helyettesítés:

 ha x-ből vezet egy e él y-ba és d(y)>d(x)+l(e), akkor d(y) family: symbol">¬ d(x)+l(e)

        - a Dijkstra algoritmus szerint minden él mentén a javítást csak egyszer kell elvégezni, ha már biztosak vagyunk abban, hogy az e él kezdőpontjának d értéke utána már nem fog tovább csökkenni

   0. lépés: S ¬ {s}, T ¬ V-{s} és d(s) ¬ 0 és minden u ¹ s-re d(u) ¬ ¥
   1. lépés: javítás u₀-ból a T-beli pontokba vezető e élekre
   2. lépés: T- beli pontok közül legyen u₀ az, amelyiken a d(u) érték a legkisebb, tegyük át u₀-t T-ből S-be
   3. lépés: ha T üres, STOP, különben újra az 1. lépéstől

   - az algoritmus lépésszáma legfeljebb v²-tel arányos

III.)  - ha olyan irányított gráfot tekintünk, melyben az élhosszak között lehetnek negatív számok, de bármely irányított kör mentén az élhosszak összege nemnegatív kell, hogy legyen, Ford algoritmusát használjuk a legrövidebb út keresésére

            0. lépés: számozzuk meg az éleket 1-től e-ig, legyen i ¬ 1, és d(s) ¬ 0 és minden u¹s-re d(u) ¬ ¥

            1. lépés: a rögzített sorrendben végezzük el a Dijkstra algoritmusnál említett javítást minden élen

            2. lépés: i ¬ i+1, ha i>v, akkor STOP, különben újra az 1. lépéstől

        - az algoritmus lépésszáma ev-vel arányos

IV.)  - a Floyd algoritmussal az összes pontpár távolsága meghatározható, ehhez egy olyan súlyozott gráf kell, melyben nincs negatív összsúlyú irányított kör

  0. lépés: minden i, j rendezett párra legyen d⁽¹⁾(i, j) ¬ l(i, j), továbbá k ¬ 2

  1. lépés: minden i, j rendezett párra d^(k)(i, j) ¬ min {d^(k-1)(i, j), d^(k-1)(i, k)+ d^(k-1)(k, j)}

    2. lépés: ha k=n, akkor STOP, ellenben k ¬ k+1, és újra az 1. lépés