Alle Beispiele

Beispiele

Dijkstras kürzeste Wege in Java

Ein gewichteter Graph mit sechs Knoten: Prioritätswarteschlange, Distanzen und Java-Code bewegen sich gemeinsam, bis jede kürzeste Distanz von Knoten 0 feststeht.

Dieses Video wurde mit dem Skill Visuelle Algorithmen gemacht.

  • 1:04
  • Visuelle Algorithmen
  • Gesprochen von Kore
  • Englisch

Aus einem Prompt erstellt

Dijkstra’s shortest paths from node 0 on a small weighted graph, in Java

Transkript zum Video

How can you find the shortest distances from node 0?

This weighted graph is our input. Settled distances stay final. Orange marks executing code; green marks settled nodes.

Line 4 sets dist to 0. Line 14 finds shorter routes: 4 to 1, 1 to 2. Which node comes next?

Node 2 wins with distance 1. Through it, 1 improves to 3.

Node 1 improves dist to 8. Line 11 skips its outdated distance 4.

Node 3 reaches 5 at 14; equal or longer routes change nothing. Node 4 settles.

Now 11 + 2 beats 14, so dist becomes 13.

Node 5 settles; outdated 14 is skipped. The queue empties.

From 0, final distances are 0, 3, 1, 8, 11, 13. Dijkstra needs nonnegative weights.

Dein Thema, gezeichnet in etwa einer Minute.

Deine ersten 2 Videos sind kostenlos, je bis zu 1 Minute lang, mit Wasserzeichen. Keine Kreditkarte nötig. Das komplette Produkt, inklusive aller Stimmen und Stile.