Gennemløb
Ændret i dette gennemløb
Undersøgte kanter

  • Aktuel
  • Har en afstand
  • Brugt kant
  • Vej
  • Negativ kreds
Et klik på en knude sætter

Mere om Bellman–Ford-algoritmen

Bellman–Ford-algoritmen

Dijkstras algoritme bryder sammen, når en kant har negativ længde, som en vej, der betaler dig en afgift i stedet for at opkræve en. Det gør Bellman–Ford-algoritmen ikke: den undersøger bare hver kant igen og igen, indtil intet bliver bedre, og den kan endda se, når en kreds får afstandene til at falde for evigt. Klik på en knude for at starte fra den, og gå gennem gennemløbene trin for trin. Tryk på Afspil for at følge søgningen, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst. Hver kant er ensrettet, som pilen viser, og tallet på den er dens længde, som kan være negativ. Klik på en knude for at gøre den til start; skift klikket til Mål, og klik på en anden knude for at se den korteste vej dertil til sidst. Tallet på hver knude er dens afstand indtil nu. Sæt kryds ved Tilføj en negativ kreds for at se, hvordan Bellman–Ford finder en. 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 se en vej til sidst, 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.
  3. Sæt kryds ved Tilføj en negativ kreds for at se Bellman–Ford finde en. Ny graf laver en anden graf, du kan prøve.

Sådan virker Bellman–Ford

Giv starten afstand 0 og alle andre knuder uendelig. Lav så gennemløb: i hvert gennemløb undersøges hver kant u → v én gang. Hvis u har en afstand, og dist(u) plus kantens længde er kortere end dist(v), så sænk dist(v), og husk u som vejen dertil. Efter gennemløb k kendes hver korteste vej, der bruger højst k kanter. En korteste vej besøger hver knude højst én gang, så den har højst n − 1 kanter, og n − 1 gennemløb er altid nok. Hvis et helt gennemløb ikke ændrer noget, kan søgningen stoppe tidligt.

Sådan findes en negativ kreds

Hvis en kreds' kanter tilsammen giver mindre end nul, gør endnu en tur rundt i den altid en vej kortere, så der er slet ingen korteste vej. Det opdager Bellman–Ford: efter n − 1 gennemløb burde ét gennemløb mere ikke ændre noget. Kan en kant stadig relakseres, kan en negativ kreds nås fra starten, og følger man de huskede knuder tilbage fra den kant, kommer man ind i den. I appen tegnes kredsen med rødt.

Ofte stillede spørgsmål

Hvad er Bellman–Ford-algoritmen?

En algoritme, der finder de korteste veje fra én start til alle andre knuder i en graf, hvis kanter kan have negative længder. Den relakserer hver kant i gentagne gennemløb og melder en negativ kreds, hvis en sådan kan nås fra starten.

Hvorfor svigter Dijkstras algoritme med negative kanter?

Dijkstra gør en knudes afstand endelig, så snart den 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 gør aldrig en afstand endelig for tidligt; den bliver ved med at undersøge hver kant.

Hvorfor n − 1 gennemløb?

En korteste vej behøver aldrig besøge en knude to gange, så den har højst n − 1 kanter. Hvert gennemløb forlænger de kendte korteste veje med mindst én kant, så efter n − 1 gennemløb er de alle fundet.

Hvor hurtig er Bellman–Ford?

Hvert gennemløb undersøger alle E kanter, og der er højst V − 1 gennemløb, så arbejdet vokser med V × E. Det er langsommere end Dijkstras algoritme, og derfor bruges Bellman–Ford, når kanter kan være negative.

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