Animation: Algorithmus von Dijkstra

Animation Systems Collection -- Animations Collection

Description

Der Algorithmus von Dijkstra dient zu Berechnung der kürzesten Wege von einem Startknoten zu allen anderen Knoten eines Graphen (gerichtet oder ungerichtet).

Hierzu wird zunächst der direkte Weg vom Startknoten zu den einzelnen Knoten als kürzester Weg eingetragen. In den Folgeschritten wird immer der am billigsten zu erreichende, bislang noch nicht besuchte Knoten gewählt und getestet, ob von diesem aus andere Knoten günstiger erreicht werden können als bislang der Fall.

Am Ende entstehen die billigsten Kosten für die Wege vom Startknoten zu allen anderen Knoten, vorausgesetzt daß die Kantengewichte alle positiv sind.

Die Animation zeigt den Ablauf des Algorithmus an einem einfachen Beispielgraph. Dabei werden in jedem Schritt der aktuelle ausgeführte Befehl (im Pseudocode angegeben) sowie die davon berührten Knoten und Kanten farblich hervorgehoben.

Screen Shot(s):

Beispielgraph nach Initialisierung mit Pseudocode

Ergebnis nach der Wahl des ersten billigsten Knotens

Endergebnis des Algorithmus

Classification

• Algorithms
• Graph Algorithms

Animation Rating

You can provide a rating for this animation. The rating is performed on a scale of 1 to 10, where 10 is the highest possible grade.

1(very bad) 2 3 4 5 6 7 8 9 10(very good)

File information

Title	Algorithmus von Dijkstra
Animation URL	http://www.animal.ahrgr.de/Anims/de/dijkstra.aml
Animation Applet	Animal Applet
Animation System	Animal
Animation Type	dynamic full VCR
Supported OS(s)	Linux,MacOS,Windows 95,Windows 98,Windows ME,Windows NT,Windows 2000,Unix
Author(s)	Jens Brodowski
Date	1999-05-10
File Size size	2372 Byte
Number of Accesses:	23721
Added to DB by	Guido Rößling
Average Rating	5.5649(285 submitted ratings)
Language:	de
Number of Accesses:	23721

BibTeX bibliographic entry for citations:

@Misc{Brodowski:1999,
   author = {Jens Brodowski},
   title = {Algorithmus von Dijkstra},
   howpublished = {WWW: \url{http://www.animal.ahrgr.de/Anims/de/dijkstra.aml}},
 }