Dijkstran lyhin polku -algoritmi - yksityiskohtainen ja visuaalinen esittely

Tervetuloa! Jos olet aina halunnut oppia ja ymmärtää Dijkstran algoritmia, tämä artikkeli on sinulle. Näet, miten se toimii kulissien takana, vaiheittaisen graafisen selityksen avulla.

Sinä tulet oppimaan:

  • Kuvaajan peruskäsitteet (nopea arvostelu).
  • Mihin Dijkstran algoritmia käytetään.
  • Kuinka se toimii kulissien takana vaiheittaisten esimerkkien avulla.

Aloitetaanpa. ✨

? Johdanto kaavioihin

Aloitetaan lyhyt esittely kaavioista.

Peruskonseptit

Kaaviot ovat tietorakenteita, joita käytetään kuvaamaan "yhteyksiä" elementtiparien välillä.

  • Näitä elementtejä kutsutaan solmuiksi . Ne edustavat tosielämän esineitä, henkilöitä tai kokonaisuuksia.
  • Solmujen välisiä yhteyksiä kutsutaan reunoiksi .

Tämä on graafinen esitys kaaviosta:

Solmut on merkitty värillisillä ympyröillä ja reunat on esitetty viivoilla, jotka yhdistävät nämä ympyrät.

? Vinkki: Kaksi solmua on kytketty, jos niiden välillä on reuna.

Sovellukset

Kaaviot ovat suoraan sovellettavissa todellisiin tilanteisiin. Voisimme esimerkiksi käyttää kaavioita liikenneverkon mallintamiseen, jossa solmut edustaisivat laitoksia, jotka lähettävät tai vastaanottavat tuotteita, ja reunat edustavat teitä tai polkuja, jotka yhdistävät ne (katso alla).

Kaavioiden tyypit

Kaaviot voivat olla:

  • Ohjaamaton: jos jokaisen yhdistetyn solmuparin kohdalla voit siirtyä solmusta toiseen molempiin suuntiin.
  • Suunnattu: jos jokaisen yhdistetyn solmuparin kohdalla voit siirtyä vain yhdestä solmusta toiseen tiettyyn suuntaan. Käytämme nuolia yksinkertaisten viivojen sijasta osoittamaan suunnattuja reunoja.

? Vinkki: Tässä artikkelissa työskentelemme suuntaamattomien kaavioiden kanssa.

Painotetut kaaviot

Painodiagrammissa on kaavio, jonka reunat on "paino" tai "kustannus". Reunan paino voi edustaa etäisyyttä, aikaa tai mitä tahansa, mikä mallintaa yhdistettävän solmuparin välistä "yhteyttä".

Esimerkiksi alla olevassa painotetussa kaaviossa näet kunkin reunan vieressä sinisen numeron. Tätä numeroa käytetään vastaavan reunan painon kuvaamiseen.

? Vinkki: Nämä painot ovat välttämättömiä Dijkstran algoritmille. Näet miksi hetkessä.

? Johdatus Dijkstran algoritmiin

Nyt kun tiedät kaavioiden peruskäsitteet, aloitetaan sukeltaminen tähän hämmästyttävään algoritmiin.

  • Tarkoitus ja käyttötapaukset
  • Historia
  • Algoritmin perusteet
  • Vaatimukset

Tarkoitus ja käyttötapaukset

Dijkstran algoritmilla löydät kaaviosta lyhimmän polun solmujen välillä. Erityisesti löydät lyhimmän polun solmusta (kutsutaan "lähdesolmuksi") kaavion kaikkiin muihin solmuihin , jolloin saadaan lyhin polku.

Tätä algoritmia käytetään GPS-laitteissa lyhimmän polun löytämiseen nykyisen sijainnin ja määränpään välille. Sillä on laajat sovellukset teollisuudessa, erityisesti aloilla, jotka vaativat mallintamisverkkoja.

Historia

Tämän algoritmin loi ja julkaisi tohtori Edsger W.Dijkstra, loistava hollantilainen tietojenkäsittelijä ja ohjelmistoinsinööri.

Vuonna 1959 hän julkaisi 3-sivuisen artikkelin nimeltä "Huomautus kahdesta ongelmasta kaavioiden yhteydessä", jossa hän selitti uuden algoritminsa.

Vuonna 2001 haastattelussa tohtori Dijkstra paljasti, miten ja miksi hän suunnitteli algoritmin:

Mikä on lyhin tapa matkustaa Rotterdamista Groningeniin? Se on lyhimmän polun algoritmi, jonka suunnittelin noin 20 minuutissa. Eräänä aamuna olin ostoksilla Amsterdamissa nuoren morsiameni kanssa ja väsyneenä istuimme kahvilan terassille juomaan kupin kahvia ja mietin vain, voisinko tehdä tämän, ja sitten suunnittelin algoritmin lyhyimmälle polulle . Kuten sanoin, se oli 20 minuutin keksintö. Itse asiassa se julkaistiin vuonna 1959, kolme vuotta myöhemmin. Julkaisu on edelleen varsin mukava. Yksi syy siihen, että se on niin mukavaa, oli, että suunnittelin sen ilman lyijykynää ja paperia. Ilman lyijykynää ja paperia olet melkein pakko välttää kaikki vältettävät kompleksit. Lopulta siitä algoritmista tuli suureksi hämmästyksekseni yksi kuuluisuuteni kulmakivistä. - Lainattu artikkelissa Edsger W.Dijkstra Edsger W.Dijkstran haastattelusta.

Uskomatonta, eikö? Vain 20 minuutissa tohtori Dijkstra suunnitteli yhden kuuluisimmista algoritmeista tietojenkäsittelytieteen historiassa.

Dijkstran algoritmin perusteet

  • Dijkstran algoritmi alkaa periaatteessa valitsemastasi solmusta (lähdesolmu) ja se analysoi kaavion löytääksesi lyhimmän polun kyseisen solmun ja kaikkien muiden kaaviossa olevien solmujen välillä.
  • Algoritmi seuraa tällä hetkellä tunnettua lyhintä etäisyyttä kustakin solmusta lähdesolmuun ja päivittää nämä arvot, jos se löytää lyhyemmän polun.
  • Kun algoritmi on löytänyt lyhimmän polun lähdesolmun ja toisen solmun välillä, kyseinen solmu merkitään "vierailuksi" ja lisätään polkuun.
  • Prosessi jatkuu, kunnes kaikki kaavion solmut on lisätty polulle. Tällä tavoin meillä on polku, joka yhdistää lähdesolmun kaikkiin muihin solmuihin ja seuraa lyhyintä mahdollista polkua jokaisen solmun saavuttamiseksi.

Vaatimukset

Dijkstran algoritmi voi toimia vain sellaisten kaavioiden kanssa, joilla on positiivinen paino. Tämä johtuu siitä, että prosessin aikana reunojen painot on lisättävä lyhimmän polun löytämiseksi.

Jos kaaviossa on negatiivinen paino, algoritmi ei toimi oikein. Kun solmu on merkitty "vierailuksi", nykyinen polku kyseiseen solmuun merkitään lyhimmäksi poluksi kyseisen solmun saavuttamiseksi. Negatiiviset painot voivat muuttaa tätä, jos kokonaispainoa voidaan vähentää tämän vaiheen jälkeen.

? Esimerkki Dijkstran algoritmista

Nyt kun tiedät lisää tästä algoritmista, katsotaanpa, miten se toimii kulissien takana vaiheittaisten esimerkkien avulla.

Meillä on tämä kaavio:

Algoritmi tuottaa lyhimmän polun solmusta 0kaikkiin muihin kaavion solmuihin.

? Vinkki: Tässä kaaviossa oletetaan, että reunojen paino edustaa kahden solmun välistä etäisyyttä.

Meillä on lyhin polku solmusta 0solmuun 1, solmusta 0solmuun 2, solmusta 0toiseen 3ja niin edelleen jokaiselle kaavion solmulle.

Aluksi meillä on tämä luettelo matkoista (katso alla oleva luettelo):

  • Etäisyys lähdesolmusta itseensä on 0. Tässä esimerkissä lähdesolmu on solmu, 0mutta se voi olla mikä tahansa valitsemasi solmu.
  • Etäisyyttä lähdesolmusta kaikkiin muihin solmuihin ei ole vielä määritetty, joten käytämme äärettömyyssymbolia edustamaan tätä aluksi.

Meillä on myös tämä luettelo (katso alla), jotta voimme seurata solmuja, joita ei ole vielä käynyt (solmut, joita ei ole sisällytetty polkuun):

? Vinkki: Muista, että algoritmi on valmis, kun kaikki solmut on lisätty polulle.

Koska päätämme aloittaa solmusta 0, voimme merkitä tämän solmun vierailuksi. Vastaavasti erotamme sen pois käymättömien solmujen luettelosta ja lisäämme punaisen reunuksen vastaavaan solmuun kaaviossa:

Nyt meidän on aloitettava etäisyyden tarkistaminen solmusta 0viereisiin solmuihin. Kuten näette, nämä ovat solmuja 1ja 2(katso punaiset reunat):

? Vinkki: Tämä ei tarkoita, että lisäämme välittömästi kaksi vierekkäistä solmua lyhyimmälle polulle. Ennen kuin lisäät solmun tälle polulle, meidän on tarkistettava, onko löydetty lyhin polku sen saavuttamiseksi. Teemme yksinkertaisesti alustavan tutkimusprosessin nähdäksemme käytettävissä olevat vaihtoehdot.

Meidän täytyy päivittää etäisyydet solmusta 0solmuun 1ja solmun 2kanssa painot reunat, jotka yhdistävät ne solmuun 0(lähde solmu). Nämä painot ovat vastaavasti 2 ja 6:

Päivitettyämme vierekkäisten solmujen etäisyydet meidän on:

  • Valitse solmu, joka on lähinnä lähdesolmua nykyisten tunnettujen etäisyyksien perusteella.
  • Merkitse se vierailuksi.
  • Lisää se polulle.

Jos tarkistamme etäisyysluettelon, voimme nähdä, että solmulla 1on lyhin etäisyys lähdesolmuun (etäisyys 2), joten lisäämme sen polkuun.

Kaaviossa voimme esittää tämän punaisella reunalla:

Merkitsemme sen punaisella neliöllä luettelossa osoittamaan, että siinä on "käynyt" ja että olemme löytäneet lyhimmän polun tähän solmuun:

Rajaamme sen pois käymättömien solmujen luettelosta:

Nyt meidän on analysoitava uudet vierekkäiset solmut löytääksemme lyhimmän polun päästä niihin. Analysoimme vain solmut, jotka ovat vierekkäin solmujen kanssa, jotka ovat jo osa lyhintä polkua (polku merkitty punaisilla reunoilla).

Solmu 3ja solmu 2ovat molemmat solmujen vieressä, jotka ovat jo polussa, koska ne ovat suoraan yhteydessä solmuun 0ja 1vastaavasti, kuten alla näkyy. Nämä ovat solmut, joita analysoimme seuraavassa vaiheessa.

Koska etäisyys lähdesolmusta solmuun on jo 2kirjoitettu luetteloon, meidän ei tarvitse päivittää etäisyyttä tällä kertaa. Meidän on vain päivitettävä etäisyys lähdesolmusta uuteen viereiseen solmuun (solmu 3):

Tämä etäisyys on 7 . Katsotaanpa miksi.

Etäisyyden löytämiseksi lähdesolmusta toiseen solmuun (tässä tapauksessa solmu 3) lisätään kaikkien niiden reunojen painot, jotka muodostavat lyhyimmän polun kyseisen solmun saavuttamiseksi:

  • Solmulle 3: kokonaismatka on 7, koska lisäämme polun muodostavien reunojen painot 0 -> 1 -> 3(2 reunalle 0 -> 1ja 5 reunalle 1 -> 3).

Nyt kun meillä on etäisyys vierekkäisiin solmuihin, meidän on valittava, mikä solmu lisätään polkuun. Meidän on valittava avaamaton solmu, jonka etäisyys lähdesolmuun on lyhyin (tällä hetkellä tunnettu).

Etäisyysluettelosta voimme heti havaita, että tämä on solmu, 2jonka etäisyys on 6 :

Lisäämme sen polkuun graafisesti punaisella reunalla solmun ympärillä ja punaisella reunalla:

Merkitsemme sen myös käydyksi lisäämällä pieni punainen neliö etäisyyksien luetteloon ja ylittämällä sen käymättömien solmujen luettelosta:

Nyt meidän on toistettava prosessi löytääksesi lyhin polku lähdesolmusta uuteen viereiseen solmuun, joka on solmu 3.

Voit nähdä, että meillä on kaksi mahdollista polkua 0 -> 1 -> 3tai 0 -> 2 -> 3. Katsotaanpa, kuinka voimme päättää, mikä on lyhin tie.

Solmulla on 3jo aiemmin tallennettu etäisyys luettelossa ( 7, katso alla oleva luettelo). Tämä etäisyys oli seurausta edellisestä vaiheesta, jossa lisättiin kahden reunan painot 5 ja 2, jotka meidän oli ylitettävä polun seuraamiseksi 0 -> 1 -> 3.

Mutta nyt meillä on toinen vaihtoehto. Jos päätämme seurata polkua 0 -> 2 -> 3, meidän on noudatettava kahta reunaa 0 -> 2ja 2 -> 3painoilla 6 ja 8 ,vastaavasti,joka edustaa kokonaismatkaa 14 .

Ensimmäinen (olemassa oleva) etäisyys on selvästi lyhyempi (7 vs. 14), joten päätämme pitää alkuperäisen polun 0 -> 1 -> 3. Päivitämme etäisyyttä vain, jos uusi polku on lyhyempi.

Siksi tähän lisätään solmun polun avulla ensimmäinen vaihtoehto: 0 -> 1 -> 3.

Merkitsemme tämän solmun vierailuksi ja poistamme sen käymättömien solmujen luettelosta:

Toistamme prosessin uudelleen.

Meidän on tarkistettava uudet vierekkäiset solmut, joissa emme ole vielä käyneet. Tällä kertaa nämä solmut ovat solmu 4ja solmu, 5koska ne ovat solmun vieressä 3.

Päivitämme näiden solmujen etäisyydet lähdesolmuun ja pyrimme aina löytämään lyhyemmän polun, jos mahdollista:

  • Solmulle 4: etäisyys polusta   on 170 -> 1 -> 3 -> 4 .
  • Solmulle 5: etäisyys polusta on 220 -> 1 -> 3 -> 5 .

? Vinkki: Huomaa, että voimme harkita vain lyhimmän polun jatkamista (merkitty punaisella). Emme voi harkita polkuja, jotka vievät meidät sellaisten reunojen läpi, joita ei ole lisätty lyhyimpään polkuun (esimerkiksi emme voi muodostaa reittiä, joka kulkee reunan läpi 2 -> 3).

Meidän on valittava, mikä avaamaton solmu merkitään vierailuksi nyt. Tässä tapauksessa se on solmu, 4koska sillä on lyhin etäisyys etäisyysluettelossa. Lisätään se graafisesti kaavioon:

Merkitsemme sen myös "vierailuksi" lisäämällä luetteloon pieni punainen neliö:

Ja me erotamme sen käymättömien solmujen luettelosta:

Ja toistamme prosessin uudelleen. Tarkistamme vierekkäiset solmut: solmu 5ja solmu 6. Meidän on analysoitava jokainen mahdollinen polku, jota voimme seurata päästäksemme niihin solmuista, jotka on jo merkitty vieraille ja lisätty polulle.

Solmulle 5:

  • Ensimmäinen vaihtoehto on seurata polkua 0 -> 1 -> 3 -> 5, jonka etäisyys lähdesolmusta on 22 (2 + 5 + 15). Tämä etäisyys kirjattiin jo edellisen vaiheen etäisyysluetteloon.
  • Toinen vaihtoehto olisi seurata polkua 0 -> 1 -> 3 -> 4 -> 5, jonka etäisyys lähdesolmusta on 23 (2 + 5 + 10 + 6).

Ensimmäinen polku on selvästikin lyhyempi, joten valitsemme sen solmulle 5.

Solmulle 6:

  • Käytettävissä oleva polku on 0 -> 1 -> 3 -> 4 -> 6, jonka etäisyys lähdesolmusta on 19 (2 + 5 + 10 + 2).

Merkitsemme solmun lyhyimmällä (tällä hetkellä tunnetulla) etäisyydellä vierailulla. Tässä tapauksessa solmu 6.

Ja me erotamme sen käymättömien solmujen luettelosta:

Nyt meillä on tämä polku (merkitty punaisella):

Vain yksi solmu ei ole vielä käynyt, solmu 5. Katsotaanpa, kuinka voimme sisällyttää sen polkuun.

On olemassa kolme erilaista polkua, joita voimme kuljettaa saavuttaaksemme solmun 5polkuun lisätyistä solmuista:

  • Vaihtoehto 1:0 -> 1 -> 3 -> 5 etäisyydellä 22 (2 + 5 + 15).
  • Vaihtoehto 2:0 -> 1 -> 3 -> 4 -> 5 etäisyydellä 23 (2 + 5 + 10 + 6).
  • Vaihtoehto 3:0 -> 1 -> 3 -> 4 -> 6 -> 5 etäisyydellä 25 (2 + 5 + 10 + 2 + 6).

Valitsemme lyhimmän polun: 0 -> 1 -> 3 -> 5etäisyydellä 22 .

Merkitsemme solmun vierailuksi ja poistamme sen käymättömien solmujen luettelosta:

Ja voilà! Meillä on lopputulos, jolla on lyhyin polku solmusta 0kaavion jokaiseen solmuun.

Kaaviossa punaiset viivat merkitsevät lyhyimmälle polulle kuuluvat reunat. Sinun on noudatettava näitä reunoja seuraamaan lyhyintä polkua tietyn solmun saavuttamiseksi kaaviossa alkaen solmusta 0.

Esimerkiksi, jos haluat päästä solmuun 6alkaen solmusta 0, sinun on vain noudatettava punaisia ​​reunoja ja seuraat lyhyintä polkua 0 -> 1 -> 3 -> 4 - > 6automaattisesti.

? Yhteenvetona

  • Kaavioita käytetään mallintamaan yhteyksiä objektien, ihmisten tai entiteettien välillä. Niillä on kaksi pääelementtiä: solmut ja reunat. Solmut edustavat objekteja ja reunat edustavat näiden kohteiden välisiä yhteyksiä.
  • Dijkstran algoritmi löytää lyhimmän polun tietyn solmun (jota kutsutaan "lähdesolmuksi") ja kaikkien muiden solmujen välillä kaaviosta.
  • Tämä algoritmi käyttää reunojen painoja etsimään polun, joka minimoi lähdesolmun ja kaikkien muiden solmujen välisen kokonaismatkan (paino).

Toivon todella, että pidit artikkelistani ja pidit siitä hyödyllisenä. Nyt tiedät kuinka Dijkstran algoritmi toimii kulissien takana. Seuraa minua Twitterissä @EstefaniaCassN ja tutustu verkkokursseihini.