Endelig
I køen
Undersøgte kanter

  • Aktuel
  • I køen
  • Endelig
  • Vej
Et klik på en knude sætter

Mere om Dijkstras algoritme

Dijkstras algoritme

Dijkstras algoritme finder den korteste rute fra en start til alle andre knuder, når kanterne har længder, ligesom veje mellem byer. Den vokser udad fra starten og tager altid den nærmeste knude, den ikke er færdig med endnu. Klik på en knude for at starte fra den, vælg et mål, hvis du vil, og gå trin for trin for at se køen, se hver afstand falde, når kortere veje dukker op, og se den korteste vej komme frem. Tryk på Afspil for at se søgningen, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst. Klik på en knude for at gøre den til start; skift klikket til Mål, og klik på en anden knude for at søge efter en korteste vej dertil. Tallet på hver kant er dens længde, tallet på hver knude dens korteste afstand indtil nu, og rækken under grafen er køen, nærmeste først. Ny graf laver en anden graf; vælg, hvor mange knuder og kanter den har. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.

Sådan virker det

  1. Klik på en knude for at gøre den til start. Vil du søge efter en vej, så skift klikket til Mål, og klik på en anden knude.
  2. Tryk på Afspil, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst i søgningen.
  3. Følg køen under grafen og afstanden på hver knude. Ny graf laver en anden graf, du kan prøve.

Sådan virker Dijkstras algoritme

Giv starten afstand 0 og alle andre knuder uendelig, og sæt starten i en kø. Gentag så: tag den knude i køen, der har den mindste afstand, og gør afstanden endelig. For hver nabo, der ikke er endelig, læg kantens længde til knudens afstand. Er summen kortere end naboens afstand indtil nu, bliver den den nye afstand, knuden huskes som vejen dertil, og naboen sættes i køen, hvis den ikke var der. Når køen er tom, har hver knude, der kan nås, sin korteste afstand.

Hvorfor den nærmeste knude er endelig

Når en knude er den nærmeste i køen, må enhver anden vej dertil forlade den færdige del af grafen gennem en knude i køen, som er mindst lige så langt væk, og derefter lægge kanter til, som ikke kan være negative. Så ingen anden vej kan være kortere. Derfor er et mål også først sikkert, når det tages fra køen, ikke når det nås første gang, og derfor svigter Dijkstras algoritme med negative kanter: dér er Bellman–Ford-algoritmen nødvendig. Når hver kant har længde 1, gør Dijkstras algoritme det samme som bredde-først-søgning.

Ofte stillede spørgsmål

Hvad er Dijkstras algoritme?

En måde at finde de korteste veje fra én startknude til alle andre knuder i en graf, hvis kanter har længder på nul eller mere. Den tager igen og igen den nærmeste knude, der ikke er færdig, gør dens afstand endelig og bruger dens kanter til at forkorte naboernes afstande.

Hvorfor virker Dijkstras algoritme ikke med negative kanter?

Den gør en knudes afstand endelig, så snart knuden er den nærmeste i køen. En negativ kant, der findes senere, kan stadig føre tilbage til knuden ad en kortere vej, så den endelige afstand kan være forkert. Bellman–Ford-algoritmen kan håndtere negative kanter, så længe der ikke er en kreds med negativ sum.

Hvad er forskellen på Dijkstra og BFS?

Bredde-først-søgning tæller kanter og bruger en almindelig kø. Dijkstras algoritme lægger kantlængder sammen og bruger en prioritetskø, der altid giver den nærmeste knude. Når hver kant har længde 1, finder begge de samme afstande.

Hvor hurtig er Dijkstras algoritme?

Med en binær hob som prioritetskø vokser arbejdet med (V + E) log V for V knuder og E kanter. Med en Fibonacci-hob er det E + V log V. Appen holder køen som en sorteret liste, som er nem at vise og fin til små grafer.

Bliver min graf sendt nogen steder hen?

Nej. Grafen laves og gennemsøges i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor