Der Breitensuche-Algorithmus ist schnell, aber häufig nicht ausreichend. In vielen Fällen ist es wichtig, die unterschiedlichen Weglängen, Fahrtdauern oder Kosten zwischen den einzelnen Orten (Knoten) zu beachten. Dies leistet der Algorithmus von Dijkstra. Allerdings ist er langsamer als BFS und kann auch nur mit positiven Kantengewichten arbeiten.
Probiere den Algorithmus auf verschiedenen Graphen aus. Was würde passieren, wenn Du negative Kantengewichte benutztest?
Wenn Du zuerst ein automatisch ablaufendes Beispiel sehen willst, klicke hier.
Element bewegen | ||
Knoten hinzufügen | ||
Kante hinzufügen | ||
Element entfernen | ||
Kantengewicht erhöhen | ||
Kantengewicht vermindern | ||
Startknoten wählen | ||
Nächster Schritt im Algorithmusablauf | ||
Zurücksetzen |