0. Vârful Xn este marcat cu 0, vârfurile rămase sunt considerate nemarcate.
1. i = i + 1. Marcate de indexul i sunt toate nodurile nemarcate anterior, în care există arce de la vârfurile etichetate. Dacă vârful Xk este etichetat, atunci 2 este satisfăcut. În caz contrar, dacă unele noduri sunt marcate la valoarea curentă a indexului i, atunci 1 este îndeplinită. Altfel, se concluzionează că nu există o cale de la vârful XH la Xk.
2. Înapoi de-a lungul arcurilor, începând de la vârful Xk, se disting acele arce care intră în contact cu vârfurile selectate și diferența dintre greutățile lor egale cu 1.
3. Când se deplasează de la vârful XH de-a lungul arcurilor selectate, sunt construite toate cele mai scurte căi spre vârful Xk.
Wave algoritm pentru construirea celei mai scurte căi pentru un grafic ponderat
1. Vârful XH primește greutatea V = 0, numărul său fiind introdus într-o serie de numere M
vârfuri care au schimbat greutatea. Restul vârfurilor Xi primesc greutatea Vi = ∞, numerele lor nu sunt
intră în matricea M.
2. Dacă matricea M este goală, atunci pasul 3 este executat, altfel este selectat cu excepția
din el următorul vârf Xi. și greutățile vârfurilor care aparțin rezultatului G (Xi) al vârfului Xi sunt recalculate. „Xi Î G (Xi) (Vj = min (Vj Vi + lij)). Dacă greutatea Vj scade, numărul j este inclus în M. Din nou, subsecțiunea 2 este îndeplinită.
3. Dacă greutatea Vi = ∞, atunci se trage concluzia că căile de la vârful XH la vârful Xk
nu, altfel procedeul de arcare este același ca în algoritmul val
Grafic unweighted, cu excepția faptului că greutățile de diferență vârfuri Xi și Xj lij egale.
4. După selectarea arcurilor, sunt construite cele mai scurte căi, ale căror lungimi sunt egale cu Vk.
exemplu
Trimiteți-le prietenilor: