Hullám algoritmus építi a legrövidebb utat a súlyozatlan száma

0. vertex xh jelzett 0, a maradék csúcsok tekinthetők jelöletlen.

1. i = i + 1. Jelzett i index minden jelöletlen korábbi csúcsot, amelyben van egy ív vertex jelölve. Ha a jelölt csúcs Xk, akkor a követelés 2. Ellenkező esetben, ha az aktuális érték az i index jelöltük bármely csúcs, akkor a 1. igénypont szerinti. Egyébként arra a következtetésre jutottak, hogy az utat a tetején a XH XK sem.

2. Fordított áthaladását mentén ívek kezdve a felső Xk azonosítja azokat ívek, amelyek az eset, hogy a kiválasztott csúcsok, és a különbség a súlyok egyenlő 1.

3. Amikor mozog a felső XH bérelt ívek épül minden legrövidebb utak, a tetejére a XK.

Hullám algoritmus építi a legrövidebb út egy súlyozott gráf

1. A felső XH kapott tömeg V = 0, akkor lépett a tömb a M szám
felsők, változtassa meg a súlyát. A fennmaradó csúcsok Xi kapott tömeg Vi = ∞, számuk nem
adja meg a tömeges M.

2. Ha a tömb M üres, akkor az n. 3, vagy a kiválasztott a kivétel
belőle a következő vertex Xi. és átalakítjuk a súlya csúcsok tartozó végén G (Xi) Xi tetejét. „Xi Î G (Xi) (Vj = min (Vj Vi + lij)). Ha Vj tömege csökken, a számot J szereplő M ismét végre n. 2.

3. Ha a súly Vi = ∞, akkor arra a következtetésre jutottak, hogy az utat a tetején a tetején az XH Xk
Nem, különben az eljárást végzik kiemelni ívek, ugyanaz, mint a hullám algoritmus
a súlyozatlan gráf, azzal az eltéréssel, hogy a különbség súlyok csúcsok Xi és Xj egyenlő lij.

4. izolálás után ívek épített legrövidebb utak, amelynek hossza egyenlő a Vk.
példa