Dijkstra lühim tee

Vaata, kuidas Dijkstra algoritm leiab lühima tee kaalutud graafis.

Näidisarvutus — Dijkstra lühim tee

Tipp 0	0
Tipp 1	3
Tipp 2	8
Tipp 3	2
Tipp 4	8
Lühim tee	0 → 3 → 4 (cost: 8)

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Relaksatsioon on kogu algoritm; prioriteetjärjekord on ainult kiirus 🖖

Dijkstra algoritm leiab lühima tee sõlmede vahel mitte-negatiivsete kaaludega graafis. See töötab ahnelt (greedy), uuendades kaugusehinnanguid relaksatsiooni kaudu: d(v) = min(d(v), d(u) + w(u,v)). Ajaline keerukus on optimeeritud tasemele O(E + V log V), kasutades Fibonacci kuhja prioriteedijärjekorda.

Miks lähim tipp on alati kindel 🖖

Dijkstra kasvatab alguspunktist väljapoole rinnet ja valib alati lähima veel külastamata tipu. Kuna kõik kaalud on mittenegatiivsed, ei suuda ükski hilisem ümbertee võita juba leitud lühemat teed — kui tipp on kord kinnitatud, on selle kaugus lõplik ja seda ei vaadata enam üle. Seetõttu toetuvad marsruudiplaneerijad ja võrguprotokollid nagu OSPF sellele usaldusväärsete lühimate teede arvutamiseks.

Välja mõeldud kahekümne minutiga kohvikus 🖖

Edsger Dijkstra mõtles algoritmi 1956. aastal välja umbes kahekümne minutiga, ilma pliiatsi ja paberita, puhates Amsterdami kohviku terrassil. Ta otsis näiteülesannet arvutile ARMAC ja valis lühima marsruudi kahe Hollandi linna, Rotterdami ja Groningeni vahel. Kolm aastat hiljem avaldas ta selle vaevalt kolmeleheküljelises artiklis — ühes informaatika enim tsiteeritud tulemuses.

Ülesanne täielikult lahendatud

Sõlm 1 allikast ühe serva kaugusel hinnaga 4 5 sammu
Tipp 1 on lähtetipust ühe serva kaugusel kaaluga 4 — ja algoritm teatab selle kauguseks 3. Käi läbi tippude fikseerimise järjekord ja leia, kust see 3 pärineb.
1. Dijkstra algoritm fikseerib tippe kauguse järjekorras ega külasta neid kunagi uuesti. See järjekord ongi kogu algoritm ja kogu tõestus: kui tipp on fikseeritud, ei saa selleni eksisteerida odavamat teekonda, sest iga selline teekond peaks läbima mõnda fikseerimata tippu, mis on juba kaugemal.
  
  $E = {(0, 1, 4), (0, 3, 2), (1, 2, 5), (1, 3, 1), (2, 4, 3), (3, 4, 6)}$
2. Lähtetipust annavad kaks otsest serva ajutisteks kaugusteks 4 ja 2. Kumbki pole veel lõplik — need on ülempiirid.
  
  $settle 0 : d_{1} = 4, d_{3} = 2$
3. Kõige lähemal on tipp 3 kaugusega 2, seega fikseeritakse see esimesena. Selle servade lõdvendamine leiab teekonna tipuni 1 maksumusega 2 + 1 = 3, mis on parem kui otsene serv kaaluga 4. See on samm, mis vastab küsimusele: odavaim tee naabertipuni ei pruugi olla vahetult selleni viiv serv.
  
  $settle 3 (d = 2) : d_{1} = min (4, 2 + 1) = 3, d_{4} = 2 + 6 = 8$
4. Tipp 1 fikseeritakse kaugusega 3 ning sealt servade lõdvendamine jõuab tipuni 2 kaugusega 8.
  
  $settle 1 (d = 3) : d_{2} = 3 + 5 = 8$
5. Tipp 4 on kättesaadav kaugusega 8 läbi tipu 3 ning alternatiiv läbi tipu 2 maksab 8 + 3 = 11, seega jääb kehtima lühem teekond.
  
  $settle 2, 4 : d_{4} = min (8, 8 + 3) = 8 ⟹ 0 \to 3 \to 4$
Vastus

Tööriist kuvab kaugusteks 3, 8, 2, 8 ja lühimaks teekonnaks 0 → 3 → 4. Õppetund peitub tipus 1: otsene serv ei ole lühim tee ja just ahne fikseerimine teeb selle teadasaamise odavaks, mitte eksponentsiaalseks. Tagatisel on siiski üks tingimus — mittenegatiivsed kaalud. Negatiivse serva korral saab varem fikseeritud tippu hiljem parandada ning sammu 1 tõestus kukub kokku. Klõpsa negatiivse serva eelseadistusel ja vaata, kuidas see ebaõnnestub korraga mõlemas suunas: tipp 3 tagastatakse kaugusega −1, mis pole kaugus, mida ükski teekond annaks, ja teekonna taastamine loobub täielikult teatega „tee puudub — eelkäijad moodustavad tsükli“. Valed arvud ja teekonna puudumine algoritmilt, mis on tõestatavalt korrektne kohe, kui iga kaal on mittenegatiivne.

$d_{1} = 3 via node 3, not 4 direct; 0 \to 3 \to 4 = 8$

Allikad (2)

The three-page paper, in which the shortest-path algorithm is the SECOND of the two problems: E. W. Dijkstra, "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269–271, 1959.
The algorithm the negative-edge preset points you to, which tolerates negative weights and detects a negative cycle instead of answering as though there were none: R. Bellman, "On a routing problem." Quarterly of Applied Mathematics 16(1), 87–90, 1958.

42Mathi meeskond · Uuendatud 2026-06-11

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

5-tipuline linn - 5-tipuline linn: lühim tee 0→4
3×3 võrgustik - 3×3 võrgustik: mitu lühimat teed
Sügav vs lai - Sügav vs lai: ahne strateegia ebaõnnestub
Negatiivne serv - Negatiivne serv: Dijkstra algoritm võib ebaõnnestuda