Dijkstrin najkraći algoritam puta - detaljan i vizualni uvod

Dobrodošli! Ako ste oduvijek željeli naučiti i razumjeti Dijkstrin algoritam, onda je ovaj članak za vas. Vidjet ćete kako to funkcionira iza kulisa s detaljnim grafičkim objašnjenjem.

Naučit ćeš:

  • Osnovni koncepti grafikona (brzi pregled).
  • Za što se koristi Dijkstrin algoritam.
  • Kako to funkcionira iza kulisa s detaljnim primjerom.

Započnimo. ✨

? Uvod u grafikone

Krenimo s kratkim uvodom u grafikone.

Osnovni koncepti

Grafovi su podatkovne strukture koje se koriste za predstavljanje "veza" između parova elemenata.

  • Ti se elementi nazivaju čvorovi . Oni predstavljaju objekte, osobe ili entitete iz stvarnog života.
  • Veze između čvorova nazivaju se rubovima .

Ovo je grafički prikaz grafa:

Čvorovi su predstavljeni obojenim krugovima, a rubovi crtama koje povezuju te krugove.

? Savjet: Dva su čvora povezana ako postoji rub između njih.

Prijave

Grafovi su izravno primjenjivi na stvarne scenarije. Na primjer, mogli bismo koristiti grafikone za modeliranje prometne mreže gdje bi čvorovi predstavljali uređaje koji šalju ili primaju proizvode, a rubovi ceste ili staze koje ih povezuju (vidi dolje).

Vrste grafikona

Grafovi mogu biti:

  • Neusmjereno: ako za svaki par povezanih čvorova možete ići od jednog do drugog čvora u oba smjera.
  • Usmjereno: ako za svaki par povezanih čvorova možete ići samo s jednog na drugi čvor u određenom smjeru. Za predstavljanje usmjerenih bridova koristimo strelice umjesto jednostavnih linija.

Savjet: u ovom ćemo članku raditi s neusmjerenim grafikonima.

Ponderirani grafovi

Graf težina je graf čiji su rubovi imaju „težinu” ili „cijenu”. Težina ruba može predstavljati udaljenost, vrijeme ili bilo što što modelira "vezu" između para čvorova koje povezuje.

Na primjer, na ponderiranom grafikonu ispod možete vidjeti plavi broj pored svakog ruba. Ovaj se broj koristi za predstavljanje težine odgovarajućeg ruba.

? Savjet: Ove su težine ključne za Dijkstrin algoritam. Vidjet ćete zašto u samo trenu.

? Uvod u Dijkstrin algoritam

Sad kad znate osnovne pojmove grafova, krenimo u ovaj nevjerojatni algoritam.

  • Svrha i uporaba slučajeva
  • Povijest
  • Osnove algoritma
  • Zahtjevi

Svrha i uporaba slučajeva

Pomoću Dijkstrinog algoritma možete pronaći najkraći put između čvorova u grafu. Osobito možete pronaći najkraći put od čvora (koji se naziva "izvorni čvor") do svih ostalih čvorova u grafikonu , stvarajući stablo najkraćeg puta.

Ovaj se algoritam koristi u GPS uređajima za pronalaženje najkraćeg puta između trenutnog mjesta i odredišta. Ima široku primjenu u industriji, posebno u domenama koje zahtijevaju mreže za modeliranje.

Povijest

Ovaj algoritam stvorio je i objavio dr. Edsger W. Dijkstra, briljantni nizozemski informatičar i softverski inženjer.

1959. objavio je članak od 3 stranice pod naslovom "Bilješka o dva problema u vezi s grafikonima", gdje je objasnio svoj novi algoritam.

Tijekom intervjua 2001. godine, dr. Dijkstra otkrio je kako i zašto je dizajnirao algoritam:

Koji je najkraći put od Rotterdama do Groningena? To je algoritam za najkraći put koji sam osmislio za oko 20 minuta. Jednog jutra kupio sam u Amsterdamu sa svojom mladom zaručnicom i umorni smo sjeli na terasu kafića da popijemo šalicu kave i samo sam razmišljao mogu li to učiniti, a zatim sam osmislio algoritam za najkraći put . Kao što sam rekao, bio je to izum od 20 minuta. Zapravo je objavljen 1959. godine, tri godine kasnije. Publikacija je i dalje prilično lijepa. Jedan od razloga što je tako lijep bio je taj što sam ga dizajnirao bez olovke i papira. Bez olovke i papira gotovo ste prisiljeni izbjeći sve složenosti koje se mogu izbjeći. Na kraju je taj algoritam na moje veliko zaprepaštenje postao jedan od temelja moje slave. - Kao što je citirano u članku Edsger W.Dijkstra iz intervjua s Edsgerom W. Dijkstrom.

Nevjerojatno, zar ne? U samo 20 minuta, dr. Dijkstra dizajnirao je jedan od najpoznatijih algoritama u povijesti računalnih znanosti.

Osnove Dijkstrinog algoritma

  • Dijkstrin algoritam u osnovi započinje na čvoru koji ste odabrali (izvorni čvor) i on analizira graf kako bi pronašao najkraći put između tog čvora i svih ostalih čvorova u grafu.
  • Algoritam prati trenutno poznatu najkraću udaljenost od svakog čvora do izvornog čvora i ažurira te vrijednosti ako pronađe kraći put.
  • Nakon što algoritam pronađe najkraći put između izvornog čvora i drugog čvora, taj čvor se označava kao "posjećen" i dodaje na put.
  • Proces se nastavlja sve dok se svi čvorovi na grafikonu ne dodaju na stazu. Na taj način imamo put koji povezuje izvorni čvor sa svim ostalim čvorovima slijedeći najkraći mogući put do svakog čvora.

Zahtjevi

Dijkstrin algoritam može raditi samo s grafovima koji imaju pozitivne težine. To je zato što se tijekom postupka moraju dodati težine bridova kako bi se pronašao najkraći put.

Ako se na grafikonu nalazi negativna težina, algoritam neće raditi ispravno. Jednom kada je čvor označen kao "posjećen", trenutni put do tog čvora označen je kao najkraći put do tog čvora. A negativne težine mogu to promijeniti ako se ukupna težina može smanjiti nakon što se dogodi ovaj korak.

? Primjer Dijkstrinog algoritma

Sad kad znate više o ovom algoritmu, pogledajmo kako on funkcionira iza kulisa, korak po korak.

Imamo ovaj graf:

Algoritam će generirati najkraći put od čvora 0do svih ostalih čvorova na grafikonu.

? Savjet: Za ovaj ćemo graf pretpostaviti da težina bridova predstavlja udaljenost između dva čvora.

Imat ćemo najkraći put od čvora 0do čvora 1, od čvora 0do čvora 2, od čvora 0do čvora 3, i tako dalje za svaki čvor na grafu.

U početku imamo ovaj popis udaljenosti (pogledajte popis u nastavku):

  • Udaljenost od izvornog čvora do samog sebe je 0. U ovom će primjeru izvorni čvor biti čvor, 0ali to može biti bilo koji čvor koji odaberete.
  • Udaljenost od izvornog čvora do svih ostalih čvorova još nije utvrđena, pa zato u početku koristimo simbol beskonačnosti.

Imamo i ovaj popis (vidi dolje) za praćenje čvorova koji još nisu posjećeni (čvorovi koji nisu bili uključeni u stazu):

? Savjet: Imajte na umu da je algoritam dovršen nakon što su svi čvorovi dodani na stazu.

Budući da smo odabrali početak na čvoru 0, možemo ga označiti kao posjećen. Jednako tako, prekrižimo ga s popisa ne posjećenih čvorova i dodamo crveni obrub odgovarajućem čvoru u dijagramu:

Sada moramo početi provjeravati udaljenost od čvora 0do susjednih čvorova. Kao što vidite, to su čvorovi 1i 2(pogledajte crvene rubove):

Savjet: To ne znači da odmah dodajemo dva susjedna čvora na najkraći put. Prije dodavanja čvora na ovaj put, moramo provjeriti jesmo li pronašli najkraći put do njega. Jednostavno uvodimo postupak ispitivanja kako bismo vidjeli dostupne mogućnosti.

Moramo ažurirati udaljenosti od čvora 0do čvora 1i čvora 2s težinama rubova koji ih povezuju s čvorom 0(izvorni čvor). Te su težine 2, odnosno 6:

Nakon ažuriranja udaljenosti susjednih čvorova, moramo:

  • Odaberite čvor koji je najbliži izvornom čvoru na temelju trenutne poznate udaljenosti.
  • Označi kao posjećeno.
  • Dodajte je na stazu.

Ako provjerimo popis udaljenosti, možemo vidjeti da čvor 1ima najkraću udaljenost od izvornog čvora (udaljenost od 2), pa ga dodajemo na put.

Na dijagramu to možemo prikazati crvenim rubom:

Označavamo ga crvenim kvadratom na popisu da predstavljamo da je "posjećen" i da smo pronašli najkraći put do ovog čvora:

Prekrižimo ga s popisa ne posjećenih čvorova:

Sada moramo analizirati nove susjedne čvorove kako bismo pronašli najkraći put do njih. Analizirat ćemo samo čvorove koji su susjedni čvorovima koji su već dio najkraćeg puta (put označen crvenim rubovima).

Čvor 3i čvor 2su susjedni čvorovima koji su već na putu jer su izravno povezani s 0čvorom 1, odnosno čvorom , kao što možete vidjeti dolje. To su čvorovi koje ćemo analizirati u sljedećem koraku.

Budući da na popisu već imamo 2zapisanu udaljenost od izvornog čvora do čvora, ovaj put ne moramo ažurirati udaljenost. Trebamo samo ažurirati udaljenost od izvornog čvora do novog susjednog čvora (čvora 3):

Ova udaljenost je 7 . Da vidimo zašto.

Da bismo pronašli udaljenost od izvornog čvora do drugog čvora (u ovom slučaju čvora 3), dodajemo težine svih bridova koji čine najkraći put do tog čvora:

  • Za čvor 3: ukupna udaljenost je 7 jer zbrajamo težine bridova koji čine put 0 -> 1 -> 3(2 za rub 0 -> 1i 5 za rub 1 -> 3).

Sada kada imamo udaljenost do susjednih čvorova, moramo odabrati koji će čvor biti dodan na put. Moramo odabrati ne posjećeni čvor s najkraćom (trenutno poznatom) udaljenostom do izvornog čvora.

S popisa udaljenosti možemo odmah otkriti da je ovo čvor 2s udaljenostom 6 :

Dodajemo ga na stazu grafički s crvenim obrubom oko čvora i crvenim rubom:

Također ga označavamo kao posjećen dodavanjem malog crvenog kvadrata na popis udaljenosti i prekriživanjem s popisa ne posjećenih čvorova:

Sada moramo ponoviti postupak kako bismo pronašli najkraći put od izvornog čvora do novog susjednog čvora, koji je čvor 3.

Možete vidjeti da imamo dva moguća puta 0 -> 1 -> 3odn 0 -> 2 -> 3. Pogledajmo kako možemo odlučiti koji je najkraći put.

Čvor 3već ima udaljenost na popisu koja je prethodno snimljena ( 7, pogledajte popis dolje). Ova je udaljenost rezultat prethodnog koraka, gdje smo dodali utege 5 i 2 dva ruba koja smo trebali prijeći da bismo slijedili put 0 -> 1 -> 3.

Ali sada imamo drugu alternativu. Ako odlučimo slijediti put 0 -> 2 -> 3, trebali bismo slijediti dva ruba 0 -> 2i 2 -> 3s utezima 6 i 8 ,odnosno,što predstavlja ukupnu udaljenost od 14 .

Jasno je da je prva (postojeća) udaljenost kraća (7 naspram 14), pa ćemo odlučiti zadržati izvorni put 0 -> 1 -> 3. Udaljenost ažuriramo samo ako je novi put kraći.

Stoga smo dodali ovaj čvor na putu koristeći prvu alternativu: 0 -> 1 -> 3.

Označavamo ovaj čvor kao posjećen i prekrižavamo ga s popisa ne posjećenih čvorova:

Sada opet ponavljamo postupak.

Moramo provjeriti nove susjedne čvorove koje do sada nismo posjetili. Ovaj put su ti čvorovi čvor 4i čvor 5jer su uz čvor 3.

Ažuriramo udaljenosti tih čvorova do izvornog čvora, uvijek pokušavajući pronaći kraći put, ako je moguće:

  • Za čvor 4: udaljenost je 17 od staze   0 -> 1 -> 3 -> 4.
  • Za čvor 5: udaljenost je 22 od staze 0 -> 1 -> 3 -> 5.

? Savjet: Primijetite da možemo razmotriti samo produljenje najkraćeg puta (označeno crvenom bojom). Ne možemo uzeti u obzir putove koji će nas provesti kroz rubove koji nisu dodani na najkraći put (na primjer, ne možemo oblikovati putanju koja prolazi kroz rub 2 -> 3).

Moramo odabrati koji će neovisni čvor biti označen kao posjećen sada. U ovom je slučaju čvor 4jer ima najkraću udaljenost na popisu udaljenosti. Grafički ga dodajemo u dijagram:

Također ga označavamo kao "posjećen" dodavanjem malog crvenog kvadrata na popis:

I prekrižimo ga s popisa ne posjećenih čvorova:

I postupak ponavljamo opet. Provjeravamo susjedne čvorove: čvor 5i čvor 6. Moramo analizirati svaki mogući put koji možemo slijediti kako bismo ih došli do čvorova koji su već označeni kao posjećeni i dodani na put.

Za čvor 5:

  • Prva opcija je slijediti put 0 -> 1 -> 3 -> 5koji ima udaljenost 22 od izvornog čvora (2 + 5 + 15). Ta je udaljenost već zabilježena na popisu udaljenosti u prethodnom koraku.
  • Druga opcija bila bi slijediti put 0 -> 1 -> 3 -> 4 -> 5koji ima udaljenost 23 od izvornog čvora (2 + 5 + 10 + 6).

Jasno je da je prvi put kraći, pa ga odabiremo za čvor 5.

Za čvor 6:

  • Dostupna putanja je 0 -> 1 -> 3 -> 4 -> 6koja ima udaljenost 19 od izvornog čvora (2 + 5 + 10 + 2).

Čvor označavamo s najkraćom (trenutno poznatom) udaljenost koja je posjećena. U ovom slučaju, čvor 6.

I prekrižimo ga s popisa ne posjećenih čvorova:

Sada imamo ovaj put (označen crvenom bojom):

Samo jedan čvor još nije posjećen, čvor 5. Pogledajmo kako to možemo uključiti u put.

Postoje tri različite staze kojima možemo doći do čvora 5iz čvorova koji su dodani na stazu:

  • Opcija 1:0 -> 1 -> 3 -> 5 s udaljenostom 22 (2 + 5 + 15).
  • Opcija 2:0 -> 1 -> 3 -> 4 -> 5 s udaljenostom od 23 (2 + 5 + 10 + 6).
  • Opcija 3:0 -> 1 -> 3 -> 4 -> 6 -> 5 s udaljenostom od 25 (2 + 5 + 10 + 2 + 6).

Odabiremo najkraći put: 0 -> 1 -> 3 -> 5s udaljenostom od 22 .

Čvor označavamo kao posjećen i prekrižavamo ga s popisa ne posjećenih čvorova:

I voilà! Konačni smo rezultat s najkraćim putem od čvora 0do svakog čvora na grafu.

Na dijagramu crvene crte označavaju rubove koji pripadaju najkraćem putu. Morate slijediti ove rubove da biste slijedili najkraći put do zadanog čvora na grafikonu počevši od čvora 0.

Na primjer, ako želite doći do čvora 6počevši od čvora 0, samo trebate slijediti crvene rubove i automatski ćete slijediti najkraći put 0 -> 1 -> 3 -> 4 - > 6.

? Sažeto

  • Grafovi se koriste za modeliranje veza između objekata, ljudi ili entiteta. Imaju dva glavna elementa: čvorove i rubove. Čvorovi predstavljaju objekte, a rubovi veze između tih objekata.
  • Dijkstrin algoritam pronalazi najkraći put između određenog čvora (koji se naziva "izvorni čvor") i svih ostalih čvorova u grafu.
  • Ovaj algoritam koristi težine rubova kako bi pronašao put koji minimizira ukupnu udaljenost (težinu) između izvornog čvora i svih ostalih čvorova.

Doista se nadam da vam se svidio moj članak i da vam je pomogao. Sada znate kako Dijkstrin algoritam djeluje iza kulisa. Pratite me na Twitteru @EstefaniaCassN i provjerite moje internetske tečajeve.