Dijkstra īsākā ceļa algoritms - detalizēts un vizuāls ievads

Laipni lūdzam! Ja jūs vienmēr esat vēlējies uzzināt un saprast Dijkstra algoritmu, tad šis raksts ir domāts jums. Jūs redzēsiet, kā tas darbojas aiz ainas, ar pakāpenisku grafisku skaidrojumu.

Tu iemācīsies:

  • Grafika pamatjēdzieni (ātra pārskatīšana).
  • Kam tiek izmantots Dijkstra algoritms.
  • Kā tas darbojas aizkulisēs, izmantojot soli pa solim piemēru.

Sāksim. ✨

? Ievads grafikos

Sāksim ar īsu grafiku ievadu.

Pamatjēdzieni

Grafiki ir datu struktūras, ko izmanto, lai attēlotu "savienojumus" starp elementu pāriem.

  • Šos elementus sauc par mezgliem . Tie pārstāv reālās dzīves objektus, personas vai vienības.
  • Savienojumus starp mezgliem sauc par malām .

Šis ir grafika grafiskais attēlojums:

Mezgli ir attēloti ar krāsainiem apļiem, bet malas - ar līnijām, kas savieno šos apļus.

? Padoms: divi mezgli ir savienoti, ja starp tiem ir mala.

Pieteikumi

Grafiki ir tieši piemērojami reālās situācijas scenārijiem. Piemēram, mēs varētu izmantot grafikus, lai modelētu transporta tīklu, kur mezgli apzīmē iekārtas, kas sūta vai saņem produktus, un malas - ceļus vai ceļus, kas tos savieno (skat. Zemāk).

Grafiku veidi

Diagrammas var būt:

  • Nevirzīts: ja katram savienoto mezglu pārim varat pāriet no viena mezgla uz otru abos virzienos.
  • Virzīts: ja katram savienoto mezglu pārim varat pāriet tikai no viena mezgla uz citu noteiktā virzienā. Lai attēlotu virzītās malas, vienkāršu līniju vietā mēs izmantojam bultiņas.

? Padoms: šajā rakstā mēs strādāsim ar nenovirzītiem grafikiem.

Svērtie grafiki

Svars diagramma ir diagramma, kura malas ir "svars" vai "izmaksas". Malas svars var attēlot attālumu, laiku vai jebko citu, kas modelē "savienojumu" starp savienoto mezglu pāri.

Piemēram, zemāk esošajā svērtajā diagrammā blakus katrai malai varat redzēt zilu skaitli. Šis skaitlis tiek izmantots, lai attēlotu attiecīgās malas svaru.

? Padoms. Šie svari ir svarīgi Dijkstra algoritmam. Jūs redzēsiet, kāpēc tikai vienā mirklī.

? Ievads Dijkstra algoritmā

Tagad, kad jūs zināt grafu pamatjēdzienus, sāksim ienirt šajā apbrīnojamajā algoritmā.

  • Mērķa un lietošanas gadījumi
  • Vēsture
  • Algoritma pamati
  • Prasības

Mērķa un lietošanas gadījumi

Izmantojot Dijkstra algoritmu, diagrammā varat atrast īsāko ceļu starp mezgliem. Konkrēti, jūs varat atrast īsāko ceļu no mezgla (ko sauc par "avota mezglu") līdz visiem citiem diagrammas mezgliem , veidojot īsākā ceļa koku.

Šis algoritms tiek izmantots GPS ierīcēs, lai atrastu īsāko ceļu starp pašreizējo atrašanās vietu un galamērķi. Tam ir plaši pielietojumi rūpniecībā, īpaši jomās, kurās nepieciešami modeļu tīkli.

Vēsture

Šo algoritmu izveidoja un publicēja izcils holandiešu datorzinātnieks un programmatūras inženieris Dr. Edsgers W. Dijkstra.

1959. gadā viņš publicēja rakstu uz 3 lappusēm ar nosaukumu "Piezīme par divām problēmām saistībā ar grafikiem", kur viņš paskaidroja savu jauno algoritmu.

Intervijas laikā 2001. gadā Dr Dijkstra atklāja, kā un kāpēc viņš izstrādāja algoritmu:

Kāds ir īsākais ceļojuma veids no Roterdamas uz Groningenu? Tas ir īsākā ceļa algoritms, kuru es izstrādāju apmēram 20 minūtēs. Kādu rītu es iepirkos Amsterdamā kopā ar savu jauno līgavaini un noguris, mēs apsēdāmies kafejnīcas terasē, lai iedzertu tasi kafijas, un es tikai domāju, vai es to varētu izdarīt, un pēc tam es izstrādāju īsākā ceļa algoritmu . Kā jau teicu, tas bija 20 minūšu izgudrojums. Faktiski tas tika publicēts 1959. gadā, trīs gadus vēlāk. Publikācija joprojām ir diezgan jauka. Viens no iemesliem, kāpēc tas ir tik jauki, bija tas, ka es to veidoju bez zīmuļa un papīra. Bez zīmuļa un papīra jūs gandrīz esat spiests izvairīties no visām iespējamām sarežģītībām. Galu galā šis algoritms, man par lielu izbrīnu, kļuva par vienu no manas slavas stūrakmeņiem. - Kā citēts rakstā Edsger W.Dijkstra no Intervija ar Edsger W. Dijkstra.

Neticami, vai ne? Tikai 20 minūtēs doktors Dijkstra izstrādāja vienu no slavenākajiem algoritmiem datorzinātņu vēsturē.

Dijkstra algoritma pamati

  • Dijkstra algoritms pamatā sākas ar izvēlēto mezglu (avota mezglu), un tas analizē diagrammu, lai atrastu īsāko ceļu starp šo mezglu un visiem pārējiem diagrammas mezgliem.
  • Algoritms seko pašlaik zināmajam īsākajam attālumam no katra mezgla līdz avota mezglam, un, ja atrod īsāku ceļu, tas atjaunina šīs vērtības.
  • Kad algoritms ir atradis īsāko ceļu starp avota mezglu un citu mezglu, šis mezgls tiek atzīmēts kā "apmeklēts" un pievienots ceļam.
  • Process turpinās, līdz visi diagrammas mezgli ir pievienoti ceļam. Tādā veidā mums ir ceļš, kas savieno avota mezglu ar visiem pārējiem mezgliem, sekojot pēc iespējas īsākam ceļam, lai sasniegtu katru mezglu.

Prasības

Dijkstra algoritms var darboties tikai ar grafikiem, kuriem ir pozitīvs svars. Tas notiek tāpēc, ka procesa laikā jāpievieno malu svars, lai atrastu īsāko ceļu.

Ja diagrammā ir negatīvs svars, tad algoritms nedarbosies pareizi. Kad mezgls ir atzīmēts kā "apmeklēts", pašreizējais ceļš uz šo mezglu tiek atzīmēts kā īsākais ceļš, lai sasniegtu šo mezglu. Negatīvie svari to var mainīt, ja kopējo svaru var samazināt pēc šī soļa iestāšanās.

? Dižkstra algoritma piemērs

Tagad, kad jūs zināt vairāk par šo algoritmu, redzēsim, kā tas darbojas aiz ainas, izmantojot soli pa solim sniegtu piemēru.

Mums ir šī diagramma:

Algoritms ģenerēs īsāko ceļu no mezgla 0līdz visiem pārējiem diagrammas mezgliem.

? Padoms: Šajā grafikā mēs pieņemsim, ka malu svars norāda attālumu starp diviem mezgliem.

Mums būs īsākais ceļš no mezgla 0uz mezglu 1, no mezgla 0uz mezglu 2, no mezgla 0uz mezglu 3utt.

Sākumā mums ir šāds attālumu saraksts (lūdzu, skatiet sarakstu zemāk):

  • Attālums no avota mezgla līdz pašam ir 0. Šajā piemērā avota mezgls būs mezgls, 0bet tas var būt jebkurš izvēlētais mezgls.
  • Attālums no avota mezgla līdz visiem pārējiem mezgliem vēl nav noteikts, tāpēc mēs sākotnēji izmantojam bezgalības simbolu.

Mums ir arī šis saraksts (skatīt zemāk), lai sekotu līdzi mezgliem, kuri vēl nav apmeklēti (mezgli, kas nav iekļauti ceļā):

? Padoms: atcerieties, ka algoritms ir pabeigts, kad visi mezgli ir pievienoti ceļam.

Tā kā mēs izvēlamies sākt no mezgla 0, mēs varam atzīmēt šo mezglu kā apmeklētu. Līdzīgi mēs to izslēdzam no neapmeklēto mezglu saraksta un diagrammā attiecīgajam mezglam pievienojam sarkanu apmali:

Tagad mums jāsāk pārbaudīt attālums no mezgla 0līdz blakus esošajiem mezgliem. Kā redzat, tie ir mezgli 1un 2(skatiet sarkanās malas):

? Padoms: Tas nenozīmē, ka mēs uzreiz pievienojam divus blakus esošos mezglus īsākajam ceļam. Pirms mezgla pievienošanas šim ceļam mums jāpārbauda, ​​vai esam atraduši īsāko ceļu, lai to sasniegtu. Mēs vienkārši veicam sākotnējo pārbaudes procesu, lai redzētu pieejamās iespējas.

Mums jāatjaunina attālumi no mezgla 0līdz mezglam 1un mezglam 2ar to malu svaru, kas savieno tos ar mezglu 0(avota mezglu). Šie svari ir attiecīgi 2 un 6:

Pēc blakus esošo mezglu attālumu atjaunināšanas mums:

  • Balstoties uz pašreizējiem zināmajiem attālumiem, atlasiet mezglu, kas ir vistuvāk avota mezglam.
  • Atzīmējiet to kā apmeklētu.
  • Pievienojiet to ceļam.

Pārbaudot attālumu sarakstu, mēs varam redzēt, ka mezglam 1ir īsākais attālums līdz avota mezglam (attālums ir 2), tāpēc mēs to pievienojam ceļam.

Diagrammā mēs to varam attēlot ar sarkanu malu:

Mēs to atzīmējam ar sarkanu kvadrātu sarakstā, lai parādītu, ka tas ir "apmeklēts" un ka esam atraduši īsāko ceļu uz šo mezglu:

Mēs to izslēdzam no neapmeklēto mezglu saraksta:

Tagad mums ir jāanalizē jaunie blakus esošie mezgli, lai atrastu īsāko ceļu, lai tos sasniegtu. Mēs analizēsim tikai tos mezglus, kas atrodas blakus mezgliem, kuri jau ir daļa no īsākā ceļa (ceļš ir atzīmēts ar sarkanām malām).

Mezgls 3un mezgls 2ir blakus mezgliem, kas jau atrodas ceļā, jo tie ir tieši saistīti ar mezglu 0un mezglu 1attiecīgi, kā redzat zemāk. Tie ir mezgli, kurus mēs analizēsim nākamajā solī.

Tā kā mūsu sarakstā jau ir ierakstīts attālums no avota mezgla līdz mezglam 2, mums šoreiz nav jāatjaunina attālums. Mums tikai jāatjaunina attālums no avota mezgla līdz jaunajam blakus esošajam mezglam (mezglam 3):

Šis attālums ir 7 . Apskatīsim, kāpēc.

Lai atrastu attālumu no avota mezgla līdz citam mezglam (šajā gadījumā mezglam 3), mēs pievienojam visu to malu svaru, kas veido īsāko ceļu, lai sasniegtu šo mezglu:

  • Mezglam 3: kopējais attālums ir 7, jo mēs pievienojam to malu svaru, kas veido ceļu 0 -> 1 -> 3(2 malai 0 -> 1un 5 malai 1 -> 3).

Tagad, kad mums ir attālums līdz blakus esošajiem mezgliem, mums jāizvēlas, kurš mezgls tiks pievienots ceļam. Mums jāizvēlas neapmeklētais mezgls ar īsāko (pašlaik zināmo) attālumu līdz avota mezglam.

No attālumu saraksta mēs varam uzreiz noteikt, ka tas ir mezgls 2ar attālumu 6 :

Mēs to grafiski pievienojam ceļam ar sarkanu apmali ap mezglu un sarkanu malu:

Mēs arī atzīmējam to kā apmeklētu, attālumu sarakstā pievienojot nelielu sarkanu kvadrātu un izslēdzot to no neapmeklēto mezglu saraksta:

Tagad mums jāatkārto process, lai atrastu īsāko ceļu no avota mezgla uz jauno blakus esošo mezglu, kas ir mezgls 3.

Var redzēt, ka mums ir divi iespējamie ceļi 0 -> 1 -> 3vai 0 -> 2 -> 3. Apskatīsim, kā mēs varam izlemt, kurš ir īsākais ceļš.

Mezglā 3jau ir ierakstīts iepriekš ierakstītais attālums ( 7, skatiet sarakstu zemāk). Šis attālums bija iepriekšējā soļa rezultāts, kur mēs pievienojām 5. un 2. svaru no divām malām, kuras mums bija jāšķērso, lai sekotu ceļam 0 -> 1 -> 3.

Bet tagad mums ir vēl viena alternatīva. Ja izvēlēsimies iet pa ceļu 0 -> 2 -> 3, mums būs jāievēro divas malas 0 -> 2un 2 -> 3ar 6. un 8. svaru ,attiecīgi,kas ir kopējais attālums 14 .

Skaidrs, ka pirmais (esošais) attālums ir mazāks (7 pret 14), tāpēc mēs izvēlēsimies saglabāt sākotnējo ceļu 0 -> 1 -> 3. Mēs atjauninām attālumu tikai tad, ja jaunais ceļš ir īsāks.

Tāpēc, mēs pievienot šo mezglu uz ceļa, izmantojot pirmo alternatīvu: 0 -> 1 -> 3.

Mēs atzīmējam šo mezglu kā apmeklētu un izslēdzam to no neapmeklēto mezglu saraksta:

Tagad mēs atkārtojam procesu vēlreiz.

Mums jāpārbauda jaunie blakus esošie mezgli, kurus līdz šim neesam apmeklējuši. Šoreiz šie mezgli ir mezgls 4un mezgls, 5jo tie atrodas blakus mezglam 3.

Mēs atjauninām šo mezglu attālumus līdz avota mezglam, vienmēr mēģinot atrast īsāku ceļu, ja iespējams:

  • Mezglam 4: attālums ir 17 no ceļa   0 -> 1 -> 3 -> 4.
  • Mezglam 5: attālums ir 22 no ceļa 0 -> 1 -> 3 -> 5.

? Padoms. Ievērojiet, ka mēs varam apsvērt tikai īsākā ceļa pagarināšanu (atzīmēts ar sarkanu). Mēs nevaram apsvērt ceļus, kas mūs ved cauri malām, kas nav pievienotas īsākajam ceļam (piemēram, mēs nevaram izveidot ceļu, kas iet caur malu 2 -> 3).

Mums jāizvēlas, kurš neapmeklētais mezgls tagad tiks atzīmēts kā apmeklēts. Šajā gadījumā tas ir mezgls, 4jo tā sarakstā ir īsākais attālums. Mēs to grafiski pievienojam diagrammā:

Mēs to atzīmējam arī kā "apmeklēts", sarakstā pievienojot nelielu sarkanu kvadrātu:

Un mēs to izslēdzam no neapmeklēto mezglu saraksta:

Un mēs atkārtojam procesu vēlreiz. Mēs pārbaudām blakus esošos mezglus: mezglu 5un mezglu 6. Mums ir jāanalizē katrs iespējamais ceļš, pa kuru varam sekot, lai sasniegtu tos no mezgliem, kuri jau ir atzīmēti kā apmeklēti un pievienoti ceļam.

Mezglam 5:

  • Pirmais variants ir sekot ceļam 0 -> 1 -> 3 -> 5, kura attālums no avota mezgla ir 22 (2 + 5 + 15). Šis attālums jau bija ierakstīts distanču sarakstā iepriekšējā solī.
  • Otra iespēja būtu sekot ceļam 0 -> 1 -> 3 -> 4 -> 5, kura attālums no avota mezgla ir 23 (2 + 5 + 10 + 6).

Skaidrs, ka pirmais ceļš ir īsāks, tāpēc mēs to izvēlamies mezglam 5.

Mezglam 6:

  • Pieejamais ceļš ir 0 -> 1 -> 3 -> 4 -> 6, kura attālums no avota mezgla ir 19 (2 + 5 + 10 + 2).

Mēs atzīmējam mezglu ar īsāko (šobrīd zināmo) attālumu kā apmeklētu. Šajā gadījumā mezgls 6.

Un mēs to izslēdzam no neapmeklēto mezglu saraksta:

Tagad mums ir šis ceļš (atzīmēts ar sarkanu):

Tikai viens mezgls vēl nav apmeklēts, mezgls 5. Apskatīsim, kā mēs to varam iekļaut ceļā.

Ir trīs dažādi ceļi, pa kuriem mēs varam nokļūt, lai sasniegtu mezglu 5no ceļā pievienotajiem mezgliem:

  • 1. variants:0 -> 1 -> 3 -> 5 ar attālumu 22 (2 + 5 + 15).
  • 2. variants:0 -> 1 -> 3 -> 4 -> 5 ar attālumu 23 (2 + 5 + 10 + 6).
  • 3. variants:0 -> 1 -> 3 -> 4 -> 6 -> 5 ar attālumu 25 (2 + 5 + 10 + 2 + 6).

Mēs izvēlamies īsāko ceļu: 0 -> 1 -> 3 -> 5ar attālumu 22 .

Mēs atzīmējam mezglu kā apmeklētu un izslēdzam to no neapmeklēto mezglu saraksta:

Un voilà! Mums ir galarezultāts ar īsāko ceļu no mezgla 0uz katru diagrammas mezglu.

Diagrammā sarkanās līnijas iezīmē malas, kas pieder pie īsākā ceļa. Jums jāievēro šīs malas, lai ietu pa īsāko ceļu, lai sasniegtu doto mezglu diagrammā, sākot no mezgla 0.

Piemēram, ja vēlaties sasniegt mezglu, 6sākot no mezgla 0, jums vienkārši jāievēro sarkanās malas, un jūs 0 -> 1 -> 3 -> 4 - > 6automātiski ejat pa īsāko ceļu .

? Kopsavilkumā

  • Grafikus izmanto, lai modelētu savienojumus starp objektiem, cilvēkiem vai entītijām. Viņiem ir divi galvenie elementi: mezgli un malas. Mezgli attēlo objektus, bet malas - savienojumus starp šiem objektiem.
  • Dijkstra algoritms diagrammā atrod īsāko ceļu starp norādīto mezglu (ko sauc par "avota mezglu") un visiem pārējiem mezgliem.
  • Šis algoritms izmanto malu svaru, lai atrastu ceļu, kas samazina kopējo attālumu (svaru) starp avota mezglu un visiem citiem mezgliem.

Es ļoti ceru, ka jums patika mans raksts un jums tas noderēja. Tagad jūs zināt, kā Dijkstra algoritms darbojas aizkulisēs. Seko man Twitter vietnē @ EstefaniaCassN un pārbaudi manus tiešsaistes kursus.