Pronađite najkraći put između dviju točaka na grafikonu s Dijkstrinim algoritmom

Pronalaženje najkraćeg puta između dviju točaka na grafu čest je problem u podatkovnim strukturama, posebno kada se radi o optimizaciji.

Graf je niz čvorova povezanih bridovima. Grafovi mogu biti ponderirani (rubovi nose vrijednosti) i usmjereni (rubovi imaju smjer).

Neke su od ovih primjena optimizacija putanje leta ili 6 stupnjeva Kevina Bacona.

Dijkstrin algoritam

Najčešće rješenje za ovaj problem je Dijkstrin algoritam koji ažurira najkraći put između trenutnog čvora i svih njegovih susjeda.

Nakon ažuriranja udaljenosti svih susjeda premješta se na čvor s najmanjom udaljenostom i ponavlja postupak sa svim ne posjećenim susjedima. Taj se postupak nastavlja dok se ne posjeti cijeli graf.

Slika razine koda

Korak 0:

Naš graf mora biti postavljen tako da možemo bilježiti tražene vrijednosti. Na bilo kojem rubu imamo udaljenost između dva čvora koja povezuje. Na bilo kojem čvoru imamo najkraću udaljenost od početnog čvora.

Postavimo vrijednost na svakom čvoru na pozitivnu beskonačnost, a vrijednost na početnom čvoru postavimo na nulu.

Korak 1:

Pogledajte sve čvorove izravno susjedne početnom čvoru. Vrijednosti koje nose rubovi koji povezuju početak i ove susjedne čvorove su najkraće udaljenosti do svakog pojedinog čvora.

Snimite ove udaljenosti na čvor - prepisivanje beskonačnosti - i također prekrižite čvorove, što znači da je pronađena njihova najkraća staza.

Korak 2:

Odaberite jedan od čvorova kojem je izračunat najkraći put, mi ćemo to nazvati naš pivot. Pogledajte čvorove u susjedstvu (nazvat ćemo ih odredišnim čvorovima) i udaljenosti koje ih razdvajaju.

Za svaki odredišni čvor:

  • Ako vrijednost u osovini plus vrijednost ruba koja je povezuje iznosi manje od vrijednosti odredišnog čvora, ažurirajte njezinu vrijednost jer je pronađena nova kraća staza.
  • Ako su istražene sve rute do ovog odredišnog čvora, može se prekrižiti.

Korak 3:

Ponavljajte korak 2 dok se ne prekriže svi čvorovi. Sada imamo graf na kojem će vrijednosti koje se čuvaju u bilo kojem čvoru biti najkraća udaljenost od početnog čvora.

Više informacija:

Više o Dijkstrinom algoritmu

Ostali algoritmi s najkraćim putem