Trumpiausias Dijkstros kelio algoritmas - išsami ir vizuali įžanga

Sveiki! Jei visada norėjote išmokti ir suprasti „Dijkstra“ algoritmą, tai šis straipsnis skirtas jums. Pamatysite, kaip tai veikia užkulisiuose, pateikdami nuoseklų grafinį paaiškinimą.

Tu išmoksi:

  • Pagrindinės grafiko sąvokos (greita apžvalga).
  • Kam naudojamas Dijkstros algoritmas.
  • Kaip tai veikia užkulisiuose, pateikiant žingsnis po žingsnio pavyzdį.

Pradėkime. ✨

? Įvadas į grafikus

Pradėkime nuo trumpo grafikų įvado.

Pagrindinės sąvokos

Grafikai yra duomenų struktūros, naudojamos „ryšiams“ tarp elementų porų vaizduoti.

  • Šie elementai vadinami mazgais . Jie vaizduoja realaus gyvenimo objektus, asmenis ar subjektus.
  • Ryšiai tarp mazgų vadinami kraštais .

Tai grafinis grafiko vaizdas:

Mazgai vaizduojami spalvotais apskritimais, o kraštai - linijomis, jungiančiomis šiuos apskritimus.

? Patarimas: Du mazgai yra sujungti, jei tarp jų yra kraštas.

Programos

Grafikai yra tiesiogiai taikomi realaus pasaulio scenarijams. Pavyzdžiui, naudodamiesi grafikais galėtume modeliuoti transporto tinklą, kuriame mazgai būtų objektai, siunčiantys ar priimantys produktus, o kraštai - kelius ar kelius, kurie juos sujungia (žr. Toliau).

Grafikų tipai

Grafikai gali būti:

  • Nenukreiptas: jei kiekvienai sujungtų mazgų porai galite pereiti iš vieno mazgo į kitą abiem kryptimis.
  • Nukreipta: jei kiekvienai sujungtų mazgų porai galite pereiti tik iš vieno mazgo į kitą tam tikra kryptimi. Mes nurodome rodykles vietoj paprastų linijų, kad vaizduotume nukreiptus kraštus.

? Patarimas: šiame straipsnyje dirbsime su nenukreiptais grafikais.

Svertiniai grafikai

Svoris grafikas yra grafikas, kurio kraštai turi "svorio" arba "kaina". Briaunos svoris gali atspindėti atstumą, laiką ar bet ką, kas modeliuoja „ryšį“ tarp jungiamų mazgų poros.

Pavyzdžiui, žemiau esančiame svertiniame grafike šalia kiekvieno krašto galite pamatyti mėlyną skaičių. Šis skaičius naudojamas atitinkamo krašto svoriui atspindėti.

? Patarimas: šie svoriai yra būtini „Dijkstra“ algoritmui. Jūs pamatysite, kodėl tik per akimirką.

? Įvadas į Dijkstros algoritmą

Dabar, kai žinote pagrindines grafikų sąvokas, pradėkime pasinerti į šį nuostabų algoritmą.

  • Paskirtis ir naudojimo atvejai
  • Istorija
  • Algoritmo pagrindai
  • Reikalavimai

Paskirtis ir naudojimo atvejai

Naudodami Dijkstros algoritmą, grafike galite rasti trumpiausią kelią tarp mazgų. Visų pirma, galite rasti trumpiausią kelią nuo mazgo (vadinamo „šaltinio mazgu“) iki visų kitų diagramos mazgų , sukuriant trumpiausio kelio medį.

Šis algoritmas naudojamas GPS įrenginiuose, norint rasti trumpiausią kelią tarp dabartinės vietos ir kelionės tikslo. Jis plačiai pritaikomas pramonėje, ypač tose srityse, kuriose reikalingi modeliavimo tinklai.

Istorija

Šį algoritmą sukūrė ir paskelbė dr. Edsgeris W. Dijkstra, puikus olandų kompiuterių mokslininkas ir programinės įrangos inžinierius.

1959 m. Jis paskelbė 3 puslapių straipsnį „Pastaba apie dvi problemas, susijusias su grafikais“, kur paaiškino savo naująjį algoritmą.

Per interviu 2001 m. Dr. Dijkstra atskleidė, kaip ir kodėl jis sukūrė algoritmą:

Koks trumpiausias būdas keliauti iš Roterdamo į Groningeną? Tai yra trumpiausio kelio algoritmas, kurį suprojektavau maždaug per 20 minučių. Vieną rytą su jauna sužadėtine apsipirkinėjau Amsterdame ir pavargusi atsisėdome į kavinės terasą išgerti puodelio kavos, o aš tik galvojau, ar galėčiau tai padaryti, o tada sukūriau trumpiausio kelio algoritmą . Kaip jau sakiau, tai buvo 20 minučių išradimas. Iš tikrųjų jis buvo paskelbtas 1959 m., Po trejų metų. Leidinys vis dar gana gražus. Viena iš priežasčių, kodėl ji yra tokia maloni, buvo ta, kad ją suprojektavau be pieštuko ir popieriaus. Neturėdami pieštuko ir popieriaus, esate beveik priversti vengti visų vengiamų komplikacijų. Ilgainiui tas algoritmas, mano didžiai nuostabai, tapo vienu kertinių mano šlovės akmenų. - Kaip cituojama straipsnyje „Edsger W.“Dijkstra iš interviu su Edsgeriu W. Dijkstra.

Neįtikėtina, tiesa? Vos per 20 minučių daktaras Dijkstra sukūrė vieną garsiausių algoritmų kompiuterijos istorijoje.

Dijkstros algoritmo pagrindai

  • „Dijkstra“ algoritmas iš esmės prasideda nuo jūsų pasirinkto mazgo (šaltinio mazgo) ir jis analizuoja grafiką, kad surastų trumpiausią kelią tarp to mazgo ir visų kitų diagramos mazgų.
  • Algoritmas seka šiuo metu žinomą trumpiausią atstumą nuo kiekvieno mazgo iki šaltinio mazgo ir atnaujina šias vertes, jei randa trumpesnį kelią.
  • Algoritmui radus trumpiausią kelią tarp šaltinio mazgo ir kito mazgo, tas mazgas pažymimas kaip „aplankytas“ ir pridedamas prie kelio.
  • Procesas tęsiasi tol, kol visi diagramos mazgai bus pridėti prie kelio. Tokiu būdu mes turime kelią, jungiantį šaltinio mazgą su visais kitais mazgais, einant kuo trumpesniu keliu, kad pasiektumėte kiekvieną mazgą.

Reikalavimai

Dijkstros algoritmas gali veikti tik su grafikais, kurių svoris yra teigiamas . Taip yra todėl, kad proceso metu, norint rasti trumpiausią kelią, reikia pridėti kraštų svorį.

Jei grafike yra neigiamas svoris, algoritmas neveiks tinkamai. Kai mazgas pažymimas kaip „aplankytas“, dabartinis kelias į tą mazgą pažymimas kaip trumpiausias kelias pasiekti tą mazgą. Neigiami svoriai gali tai pakeisti, jei po šio žingsnio galima sumažinti bendrą svorį.

? Dijkstros algoritmo pavyzdys

Dabar, kai žinote daugiau apie šį algoritmą, pažiūrėkime, kaip jis veikia užkulisiuose, pateikdami žingsnis po žingsnio pavyzdį.

Turime šią diagramą:

Algoritmas sugeneruos trumpiausią kelią nuo mazgo 0iki visų kitų diagramos mazgų.

? Patarimas: Šiame grafike laikysime, kad briaunų svoris atspindi atstumą tarp dviejų mazgų.

Turėsime trumpiausią kelią iš mazgo 0į mazgą 1, iš mazgo 0į mazgą 2, iš mazgo 0į mazgą 3ir t. T. Kiekvienam grafiko mazgeliui.

Iš pradžių mes turime šį atstumų sąrašą (žiūrėkite toliau pateiktą sąrašą):

  • Atstumas nuo šaltinio mazgo iki savęs yra 0. Šiame pavyzdyje šaltinio mazgas bus mazgas, 0tačiau tai gali būti bet kuris jūsų pasirinktas mazgas.
  • Atstumas nuo šaltinio mazgo iki visų kitų mazgų dar nebuvo nustatytas, todėl mes naudojame begalybės simbolį tam iš pradžių atstovauti.

Mes taip pat turime šį sąrašą (žr. Toliau), kad galėtume stebėti dar neaplankytus mazgus (mazgus, kurie nebuvo įtraukti į kelią):

? Patarimas: Nepamirškite, kad algoritmas bus baigtas, kai prie kelio bus pridėti visi mazgai.

Kadangi mes pasirenkame pradėti nuo mazgo 0, galime pažymėti šį mazgą kaip aplankytą. Lygiaverčiai, mes jį pašaliname iš neaplankytų mazgų sąrašo ir prie atitinkamo mazgo diagramoje pridedame raudoną kraštą:

Dabar turime pradėti tikrinti atstumą nuo mazgo 0iki gretimų mazgų. Kaip matote, tai yra mazgai 1ir 2(žr. Raudonus kraštus):

? Patarimas: tai nereiškia, kad mes nedelsdami pridedame du gretimus mazgus prie trumpiausio kelio. Prieš pridėdami mazgą prie šio kelio, turime patikrinti, ar radome trumpiausią kelią jį pasiekti. Mes tiesiog atliekame pradinį tyrimo procesą, kad pamatytume galimas galimybes.

Turime atnaujinti atstumus nuo mazgo 0iki mazgo 1ir mazgo 2su kraštų, jungiančių juos su mazgu 0(šaltinio mazgu), svoriais . Šie svoriai yra atitinkamai 2 ir 6:

Atnaujinę gretimų mazgų atstumus, turime:

  • Pagal dabartinius žinomus atstumus pasirinkite mazgą, kuris yra arčiausiai šaltinio mazgo.
  • Pažymėkite kaip aplankytą.
  • Pridėkite jį prie kelio.

Patikrinę atstumų sąrašą galime pamatyti, kad mazgas 1turi trumpiausią atstumą iki šaltinio mazgo (2 atstumas), todėl pridedame jį prie kelio.

Diagramoje tai galime pavaizduoti raudonu kraštu:

Sąraše pažymime raudonu kvadratu, kad parodytume, jog jis „aplankytas“ ir kad radome trumpiausią kelią į šį mazgą:

Mes pašaliname jį iš nelankytų mazgų sąrašo:

Dabar turime išanalizuoti naujus gretimus mazgus, kad rastume trumpiausią kelią jiems pasiekti. Mes analizuosime tik tuos mazgus, kurie yra šalia mazgų, kurie jau yra trumpiausio kelio dalis (kelias pažymėtas raudonais kraštais).

Mazgas 3ir mazgas 2yra greta mazgų, kurie jau yra kelyje, nes jie yra tiesiogiai prijungti prie mazgo 0ir 1atitinkamai, kaip matote žemiau. Tai yra mazgai, kuriuos analizuosime kitame etape.

Kadangi atstumas nuo šaltinio mazgo iki mazgo jau yra 2įrašytas į mūsų sąrašą, šį kartą nereikia atnaujinti atstumo. Mums reikia tik atnaujinti atstumą nuo šaltinio mazgo iki naujo gretimo mazgo (mazgo 3):

Šis atstumas yra 7 . Pažiūrėkime, kodėl.

Norėdami rasti atstumą nuo šaltinio mazgo iki kito mazgo (šiuo atveju mazgo 3), pridedame visų kraštų, sudarančių trumpiausią kelią pasiekti tą mazgą, svorį:

  • Mazgui 3: bendras atstumas yra 7, nes pridedame briaunų, sudarančių kelią, svorį 0 -> 1 -> 3(2 - kraštui 0 -> 1ir 5 - kraštui 1 -> 3).

Dabar, kai turime atstumą iki gretimų mazgų, turime pasirinkti, kuris mazgas bus pridėtas prie kelio. Turime pasirinkti neaplankytą mazgą su trumpiausiu (šiuo metu žinomu) atstumu iki šaltinio mazgo.

Iš atstumų sąrašo galime iš karto nustatyti, kad tai mazgas, 2kurio atstumas 6 :

Pridedame jį prie kelio grafiškai su raudona kraštu aplink mazgą ir raudonu kraštu:

Mes taip pat pažymime jį kaip aplankytą, įtraukdami mažą raudoną kvadratą į atstumų sąrašą ir perbraukdami jį iš neaplankytų mazgų sąrašo:

Dabar turime pakartoti procesą, kad rastume trumpiausią kelią nuo šaltinio mazgo iki naujo gretimo mazgo, kuris yra mazgas 3.

Galite pamatyti, kad turime du galimus kelius 0 -> 1 -> 3arba 0 -> 2 -> 3. Pažiūrėkime, kaip mes galime nuspręsti, kuris iš jų yra trumpiausias kelias.

Mazgas sąraše 3jau turi atstumą, kuris buvo užfiksuotas anksčiau ( 7, žr. Sąrašą žemiau). Šis atstumas buvo ankstesnio žingsnio rezultatas, kai mes pridėjome 5 ir 2 svarmenis iš dviejų kraštų, kuriuos mums reikėjo kirsti, kad eitume keliu 0 -> 1 -> 3.

Bet dabar mes turime kitą alternatyvą. Jei pasirinksime eiti keliu 0 -> 2 -> 3, turėtume eiti dviem kraštais 0 -> 2ir 2 -> 3su 6 ir 8 svoriais ,atitinkamai,kuris reiškia bendrą 14 atstumą .

Akivaizdu, kad pirmasis (esamas) atstumas yra trumpesnis (7 prieš 14), todėl pasirinksime išlaikyti pradinį kelią 0 -> 1 -> 3. Atstumą atnaujiname tik tuo atveju, jei naujas kelias yra trumpesnis.

Todėl mes pridėti šį mazgą į kelią, naudojant pirmą alternatyvą: 0 -> 1 -> 3.

Pažymime šį mazgą kaip aplankytą ir pašaliname jį iš nelankytų mazgų sąrašo:

Dabar pakartojame procesą dar kartą.

Turime patikrinti naujus gretimus mazgus, kurių iki šiol neaplankėme. Šį kartą šie mazgai yra mazgas 4ir mazgas, 5nes jie yra greta mazgo 3.

Atnaujiname šių mazgų atstumus iki šaltinio mazgo, visada bandydami rasti trumpesnį kelią, jei įmanoma:

  • Mazgui 4: atstumas nuo kelio   yra 170 -> 1 -> 3 -> 4 .
  • Mazgui 5: atstumas nuo kelio yra 220 -> 1 -> 3 -> 5 .

? Patarimas: atkreipkite dėmesį, kad galime apsvarstyti tik trumpiausio kelio (pažymėto raudona spalva) pratęsimą. Negalime apsvarstyti kelių, kurie eis per kraštus, kurie nebuvo pridėti prie trumpiausio kelio (pavyzdžiui, mes negalime suformuoti kelio, einančio per kraštą 2 -> 3).

Turime pasirinkti, kuris neaplankytas mazgas dabar bus pažymėtas kaip aplankytas. Šiuo atveju tai mazgas, 4nes atstumų sąraše yra trumpiausias atstumas. Grafiškai pridedame:

Mes taip pat pažymime jį kaip „aplankytą“, į sąrašą įtraukdami mažą raudoną kvadratą:

Mes pašaliname jį iš neaplankytų mazgų sąrašo:

Ir mes pakartojame procesą dar kartą. Mes patikriname gretimus mazgus: mazgą 5ir mazgą 6. Turime išanalizuoti kiekvieną įmanomą kelią, kuriuo galime eiti, kad pasiektume juos iš mazgų, kurie jau pažymėti kaip aplankyti ir pridėti prie kelio.

Mazgui 5:

  • Pirmasis variantas yra sekti kelią 0 -> 1 -> 3 -> 5, kurio atstumas nuo šaltinio mazgo yra 22 (2 + 5 + 15). Šis atstumas jau buvo įrašytas į atstumų sąrašą ankstesniame žingsnyje.
  • Antrasis variantas būtų sekti kelią 0 -> 1 -> 3 -> 4 -> 5, kurio atstumas nuo šaltinio mazgo yra 23 (2 + 5 + 10 + 6).

Aišku, kad pirmasis kelias yra trumpesnis, todėl jį pasirenkame mazgui 5.

Mazgui 6:

  • Yra kelias 0 -> 1 -> 3 -> 4 -> 6, kurio atstumas nuo šaltinio mazgo yra 19 (2 + 5 + 10 + 2).

Mažiausiu (šiuo metu žinomu) atstumu mazgą pažymime kaip aplankytą. Šiuo atveju mazgas 6.

Mes pašaliname jį iš neaplankytų mazgų sąrašo:

Dabar turime šį kelią (pažymėtą raudonai):

Dar nebuvo aplankytas tik vienas mazgas, mazgas 5. Pažiūrėkime, kaip mes galime įtraukti jį į kelią.

Yra trys skirtingi keliai, kuriais galime pasiekti mazgą 5iš mazgų, kurie buvo pridėti prie kelio:

  • 1 variantas:0 -> 1 -> 3 -> 5 su 22 atstumu (2 + 5 + 15).
  • 2 variantas: 230 -> 1 -> 3 -> 4 -> 5 atstumu (2 + 5 + 10 + 6).
  • 3 variantas: 250 -> 1 -> 3 -> 4 -> 6 -> 5 atstumu (2 + 5 + 10 + 2 + 6).

Mes pasirenkame trumpiausią kelią: 0 -> 1 -> 3 -> 5su 22 atstumu .

Mes pažymime mazgą kaip aplankytą ir pašaliname jį iš nelankytų mazgų sąrašo:

Ir voilà! Galutinis rezultatas yra trumpiausias kelias nuo mazgo 0iki kiekvieno mazgo grafike.

Diagramoje raudonos linijos žymi kraštus, kurie priklauso trumpiausiam keliui. Turite sekti šiuos kraštus, kad eitumėte trumpiausiu keliu, kad pasiektumėte nurodytą mazgą diagramoje, pradedant nuo mazgo 0.

Pavyzdžiui, jei norite pasiekti mazgą 6pradedant nuo mazgo 0, jums tereikia sekti raudonus kraštus ir 0 -> 1 -> 3 -> 4 - > 6automatiškai eisite trumpiausiu keliu .

? Apibendrinant

  • Grafikai naudojami modeliuoti ryšius tarp objektų, žmonių ar subjektų. Jie turi du pagrindinius elementus: mazgus ir kraštus. Mazgai žymi objektus, o kraštai - ryšius tarp šių objektų.
  • Dijkstros algoritmas grafike randa trumpiausią kelią tarp nurodyto mazgo (kuris vadinamas „šaltinio mazgu“) ir visų kitų mazgų.
  • Šis algoritmas naudoja kraštų svorius, kad surastų kelią, kuris sumažina bendrą atstumą (svorį) tarp šaltinio mazgo ir visų kitų mazgų.

Labai tikiuosi, kad jums patiko mano straipsnis ir jis buvo naudingas. Dabar jūs žinote, kaip Dijkstros algoritmas veikia užkulisiuose. Sekite mane „Twitter“ @EstefaniaCassN ir peržiūrėkite mano internetinius kursus.