Dijkstra.s algoritmi on suosittu menetelmä, jota käytetään tietojenkäsittelytieteessä löytää lyhin polku solmujen välillä kaaviossa. Sitä sovelletaan laajalti verkon reitityksessä, karttanavigaatiossa ja erilaisissa optimointiongelmissa. Tämä artikkeli tarjoaa vaiheittaisen yleiskuvan siitä, miten tehdä laskelmia käyttäen Dijkstra... algoritmi määrittää tehokkaimman polun.

Algoritmin ymmärtäminen

Algoritmi toimii iteratiivisesti valitsemalla solmun pienimmällä alustavalla etäisyydellä, sitten päivittämällä etäisyydet sen naapurin solmuja. Se jatkuu kunnes lyhin polku kohdesolmu löytyy tai kaikki solmut on käsitelty.

Vaiheittainen laskentaprosessi

Oletetaan meillä on kaavio, jossa on solmut A, B, C, D, ja E, ja seuraavat painotetut reunat:

  • A-B: 4
  • A-C: 2
  • B-C: 1
  • B-D: 5
  • C-D: 8
  • C-E: 10
  • D-E: 2

Aloitetaan solmusta A, alustetaan etäisyydet: A = 0, muut = äärettömyys. Merkitse kaikki solmut näkymättömiksi.

Iteraatio 1

Valitse solmukohta A (etäisyys 0). Päivitä naapurisolmut B ja C:

Välimatka B: 4 (A + 4), C: 2 (A + 2).

Iterointi 2

Valitse solmu C (etäisyys 2). Päivitä naapurit D ja E:

Välimatka D: 10 (C + 8), E: 12 (C + 10), Mark C kuten vieraili.

Iterointi 3

Valitse solmu B (etäisyys 4). Päivitä naapuri D:

Välimatka D: 9 (B + 5), joka on vähemmän kuin aiemmin 10. Päivitä D:n etäisyys 9. Mark B kuten vieraili.

Iterointi 4

Valitse solmu D (etäisyys 9). Päivitä naapuri E:

Etäisyys E: 11 (D + 2). Päivitä E:n etäisyys 11:een D:n mukaan.

Iterointi 5

Jäljellä oleva solmu E on etäisyys 11. Mark E kuten vieraili. Lyhin polku A E on kautta solmut C, B, D, ja E yhteensä etäisyys 11.