Diskussion:Dijkstra-Algorithmus/Archiv

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Dijkstra-Algorithmus/Archiv#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:Dijkstra-Algorithmus/Archiv#Thema_1

Einleitung

"Für nicht zusammenhängende, ungerichtete Graphen kann der Abstand zu bestimmten Knoten auch unendlich sein, wenn ein Pfad zwischen Startknoten und diesen Knoten nicht existiert, dieser aber in der Knotenmenge selbst vorliegt." Diese Passage in der Einleitung finde ich etwas unklar / ungünstig formuliert... JaK 11:33, 20. Mär. 2007 (CET)

Ich denke Pfad ist hier angebrachter als Weg ... (m.W. in der Sprache der Graphentheorie ueblicher ...)

Weg oder Pfad wäre in diesem Fall egal. Zu jedem kürzesten Weg gibt es auch einen kürzesten Pfad, wenn man die Begriffe so wie in der Wikipeda definiert benutzt. Manchmal bezeichnet man mit Weg und Pfad das selbe, manchmal definiert man den Begriff Pfad dann nicht einmal (zum Beispiel Distel: "Grahentheorie"). Das definiert jeder so wie er es für richtig hält. Wir sollten uns an "unsere" Definitionen halten, da sind beide Begriffe wie oben dargestellt erlaubt. Dennoch bevorzuge ich wie du Pfad. --Coma 11:50, 23. Dez 2002 (CET)

Klärt mich mal bitte auf, aber "am nähesten" und "am nächsten" ist für mich ein Unterschied! "am nähesten" bezeichet den Knoten, der den kleinsten Abstand hat... "am nächsten" gibts doch gar nicht? Leitet sich schließlich von "dem Nächsten" ab. "einen Nächsten" (also mehrere Kanditaten) gibt es in dem Sinne (zumindest hier) nicht! Dann ist es also auch Unsinn den "am nächsten" liegenden Knoten zu wählen! Ich hoffe ich hab mich halbwegs klar ausgedrückt. Deshalb würde ich den Text doch lieber wieder in "am nähesten" ändern wollen. Gibts da Einwände oder Zuspruch? --Coma 11:41, 2. Jan 2003 (CET)

IMO gibt es nur eine Steigerungsreihe von "nahe": "näher", "am nächsten". Das gilt sowohl zeitlich und räumlich als auch für eine Reihe. -- Martin

Ok, Danke, dann sollte man das so nicht ändern! Mich stört nur der scheinbare(?) Bedeutungswandel (oder besser die Bedeutungserweiterung). Der "Nächste" übersetze ich mit "next" ins engliche... "nah" mit "near" und dann steigere ich im englichen zum "nearest". "nearest" hat dann wirklich etwas mit räumlicher "Nähe" zu tun. "am nächsten" nicht unbedingt, da es im Sinne von Nachfolger bentutzt werden kann, oder? Eventuell sollte man den Satz dann doch anders fomulieren, um hier die "räumliche" (nicht strukturelle) Nähe zum Ausdruck zu bringen? --Coma 13:22, 2. Jan 2003 (CET)

"Die effiziente Bestimmung des nächsten Knotens ist aber aufwändig zu implementieren." - Mag sein. Eher erwähnenswert scheint mir jedoch der Rechenaufwand im Verhältnis zur Knotenmenge und wie man in der Praxis damit umgeht... -- zascha

Es kommt mehr auf die Zahl der Kanten an! Die Laufzeit ist O(m+nlogn) glaube ich. Der Artikel ist sowieso ausbaufähig. --Coma 21:55, 14. Dez 2003 (CET)

Dijkstra != MST (Kruskal)

In dem Artikel wird der Dijkstra-Algorithmus mit Kruskal (minimal spannender Baum) verglichen. Diese beiden Probleme sind nicht äquivalent! Man kann ein einfaches Beispiel konstruieren, wo der Kürzeste-Pfade-Graph anders aussieht als der minimal spannende Baum.

Das ist natürlich richtig, Aber im Grunde ist der Algorithmus von Dijkstra identisch zum Algorithmus vom Prim. Dijkstra bricht lediglich ab, wenn der Zielknoten erreicht wurde und berechnet (im Falle das man wirklich den Pfad kennen möchte) nochmal den Weg zurück... Prim bricht erst ab, wenn alle Knoten besucht wurden. Prim berechnet damit einem MST und lässt sich somit mit Kruskal vergleichen. Ich schau mir die Behauptung mal an und korrigiere das ggf.

Also erstmal hab ich deine Änderung rückgängig gemacht, denn die war falsch... ich werde jetzt versuchen es etwas besser zu formulieren... --Coma 16:42, 27. Aug 2004 (CEST)

Algorithmus

das alte algorithmus war nicht korrekt. ich ahbe eine korrekte version hineingestellt. Virtualone 13:31, 17. Nov 2004 (CET)

Was ist den der Unterschied zwischen Distanz und Kosten? --Skurt 20:05, 1. Dez 2005 (CET) Vielleicht sollte man eher von Gesamtkosten sprechen, da sonst nicht klar ist das sich die Kosten der einzelnen genutzten Kanten addieren? --Skurt 20:10, 1. Dez 2005 (CET)

Grundlegende Konzepte und Verwandschaften

IMO ist der Satz "Damit findet sich eine Verwandtschaft zur Breitensuche, die ebenfalls solch ein gieriges Verhalten aufweist." nicht richtig. Wenn ich mich nicht täusche ist die Breitensuche nicht gierig, da bei der standard Breitensuche ja gar keine Heuristik vorhanden ist um einen "besseren" Folgeknoten aus der Liste potenzieller Folgeknoten auszuwählen. Die Verwandschaft von Dijkstra zum Breitensuche ist aber natürlich gegeben und zwar durch die "breite" Traversierungeigenschaft der Breitensuche. Species_8472 10:10, 01. Sep 2006 (CET)

Kurz knapp und bündig: dein Einwand ist absolut korrekt. :-) Da mir aber auf die schnelle keine schöne Formulierung für "breite Traversierung in Bezug auf den Abstand zum Startknoten" einfiel, an dieser Stelle nur ein "Sei mutig!" :-) Regnaron 16:53, 1. Sep 2006 (CEST)

Dijkstra hat mit dem Algorithmus von Prim natürlich mehr gemeinsam als mit der Breitensuche.

Verallgemeinerung Falsch

betreffend "verallgemeinerung": diese aussage ist nicht richtig.

ein MST und der Spannbaum, der beim Dijkstra rauskommt können sehrwohl verschieden sein.

ein einfaches beispiel:

A--- 1+€ --S----- 1+€ ---B
|                        |
|                        |
+--------- 1 ------------+

sei € (epsilon) eine positive zahl kleiner 1.

der MST ist definitiv entweder (AB), (BS) oder (AB), (AS) kosten des MST: 2+€

der dijkstra liefert mit startpukt S die kanten (AS) und (BS) kosten dieses spanning trees: 2+2€

ich habe diese überlegungen in den artikel eingearbeitet --Virtualone 20:42, 17. Nov 2004 (CET)

Das dürfte nicht sein, der Algorithmus von Dijkstra müsste auch den MST liefern. Ich schätze das bezog sich auf die alte Version, ich schau mir das nochmal an und prüfe, ob deine Behauptung stimmt. --Coma 21:28, 17. Nov 2004 (CET)

So, habs mir angeschaut, und nein, der Algorithmus findet durchaus einen MST. Erst wählt er T=({S},{}). Dann fügt er A oder B mit entsprechender Kante hinzu. Dann ist die kürzeste Kante, die T mit einem Knoten verbindet, der nicht in T ist, genau die Kante untenrum mit Gewicht 1 und die sowie der noch fehlende Knoten wird zu T hinzugefügt. --Coma 21:58, 17. Nov 2004 (CET)

betrachte mal genau die zeile

für jeden (u,v) aus E mache

diese schleife bearbeitet zuerst die kanten (SA) und (SB), da der ausgewählte knoten u zu beim ersten schlaufendurchlauf S ist.erst danach würde es mit a oder b weitergehen.

--Virtualone 21:45, 17. Nov 2004 (CET)

Auch deine Version liefert einen MST! Zuerst wird S aus U entfernt und A und B wegen der Kanten SA und SB hinzugefügt. Die Distanz von A und B ist dann in der Tat zunächst 1+epsilon. Dann wird A oder B aus U ausgewählt, aufgrund der Symmetrie ist es egal welcher von beiden Knoten, wir nehmen an es sei A. Dann wird die Distanz von B verringert, wegen der Kante AB. Im nächsten Schritt wird B wegen dieser Kante hinzugefügt. Das Vorgänger-Attribut enthält implizit den MST. --Coma 21:58, 17. Nov 2004 (CET)

Nein, da zu dem Zeitpunkt der algorithmus bereits terminiert hat. es werden zuerst die kanten (s,a) und danach (s,b) ausgewählt, die innere schleife lautet ja für jeden (u,v) aus E und u ist derzeit S.er kommt nie dazu die kante AB auszuwählen. klarerweise ist der teilgraph ein Spannbaum, aber nicht notwendigerweise ein minimaler Spannbaum. In dem Beispiel Darf er es auch gar nicht sein, da sonst der weg von S nach B oder A anstatt 1+€ gleich 2+€ wäre. hab ich dich endlich überzeugt? --Virtualone 22:38, 17. Nov 2004 (CET)

Der Algorithmus terminiert erst, wenn U leer ist! Aber ich sehe gerade, dass du trozdem recht hast. Hab jetzt mal mein altes Skript rausgekramt. Man da hab ich ja richtig Mist verzapft. Bisher waren Dijksrtra und Prim für mich (fast) das selbe. Logisch, der alte Algorithmus hier hat einen MST berechnet (war ja auch der von Prim), aber eben nicht unbedingt kürzeste Pfade. Aber Prim und Dijkstra funktionieren offensichtlich doch anders. Werde mich also jetzt auf Tour begeben und mal suchen, wo ich noch diesen Mist behauptet habe. Das Beispiel kann eigentlich raus, samt der Behauptung man könne damit einen MST berechnen. Es ist in diesem Fall Unsinn explizit anzugeben, dass der Algorithmus keinen MST berechnen kann. --Coma 23:16, 17. Nov 2004 (CET)

Danke für die blumen. man muss natürlich sagen, dass in 95% aller beispiele auf papier auch ein MST rauskommt. erst bei komplizierteren graphen oder absichtlich so gestellten beispielen (wie meines) ist ein unterschied zum MST da.--Virtualone 01:29, 18. Nov 2004 (CET)

Allgemeines

Hallo Virtualone! Ein herzliches Willkommenen auch von mir. Mit der neuen Version des Algorithmus von Dijkstra bin ich einverstanden. Allerdings ist nicht auf Anhieb erkennbar, warum das Weglassen der mit "#optional" gekennzeichneten Zeile nun alle Pfade liefert. Das sollte noch erwähnt werden. Außerdem sollte erwähnt werden, dass der kürzeste Pfad von "e" aus nun durch "abklappern" von "Vorgänger" durchlaufen werden kann (umgekehrt -- also von "s" aus -- ist das so noch nicht möglich). Ferner fehlt mir nun eine Anpassung des Abschnittes "Verallgemeinerung" an die neue Version. Ganz allgemein (und das war auch vorher schon leider nicht vorhanden) wäre eine rein verbale Beschreibung des Algorithmus auch hilfreich. Variablen sollten nach Möglichkeit kursiv ausgezeichnet werden. MfG --Coma 17:37, 17. Nov 2004 (CET)

Ich werde deine Verbesserungsvorschläge umsetzen, sobald ich Zeit dazu habe.

Bez. dem kursiv-schreiben: ich kenne die wiki-syntax nicht so perfekt, wie schreibe ich kursiv in einem code-block?

Da bin ich mir selber nicht sicher ob das überhaupt geht. Wenn müsste es funktionieren, wie überall sonst. Aber auch im Fließtext waren einige Dinge nicht kursiv. --Coma 21:20, 17. Nov 2004 (CET)

p.s: wie sind die gepflogenheiten bez. diskussion: schreibt man auf der diskussionsseite weiter wo sie "angefangen" hat, oder jeweis auf der des gesprächspartners? -- Virtualone 19:27, 17. Nov 2004 (CET)

Eigentlich schreibt man dorthin, wo es hingehört, auf die entsprechende Diskussionsseite. Insofern war es von mir schon falsch, direkt auf deiner Benutzerdiskussionsseite zu schreiben, aber da du neu bist, wollte ich sicher gehen, dass du es mitbekommst. Wenn man sich gegenseitig etwas zu sagen hat, schreibt man es auf die Benutzerdiskussionsseite. Aber ob man das auf einer tut, oder jeweils dem anderen auf seine schreibt, darüber lässt sich streiten. Die erste Variante hat den Vorteil, dass die Diskussion zusammenhängend ist und später leichter verfolgt werden kann. Die zweite hat den Vorteil, dass der andere von der Software benachrichtigt wird. Es ist geplant, für die Diskussion lieber eine Forum-Ähnliche Plattform zu machen, weil dass diese Mängel beheben würde, aber bis die Software soweit ist, wird es noch ein Weilchen dauern (wenn sich überhaupt jemand mal die Mühe macht, das zu implementieren). --Coma 21:20, 17. Nov 2004 (CET)

Initialisierung

Ich will ja nicht daruf rumreiten, aber...

Das initialisieren der Menge U mit {s} hat schon seinen sinn. Die laufzeit ist ja O(n*log(n)) + O(m), wobei das log(n) nur durch das "finde-minimum" mit hilfe der fibonacci-hepas erzeugt wird. die menge U klein zu halten beschleunigt den algorithmus schon, und steht meines wissens in den sauberen implementierungen auch so drinnen. korrekt ist er in beiden fällen, zumindest soweit ich das bisher beurteilen kann. ich dachte zuerst dass ein problem mit mehrfachkanten oder kanten auf sich selbst existiert, konnte jedoch kein beispiel finden. --Virtualone 01:05, 18. Nov 2004 (CET)

ein beispiel für fehlverhalten habe ich gefunden: hat der graph mehrere zusammenhangskomponenten (was du in der definition bequemerweise ausschießt), so arbeitet er danach nicht mehr korrekt. da wird für "finde minimum" dann +"unendlich" ausgewählt. wird mit U={s} begonnen und danach im "inneren if" der knoten v zu U hinzugefügt (wie in meier version), löst sich das problem mit zusammenhagskomponenten von alleine. der nicht mit s verbundene teil bleibt auf entfernung unendlich und wird auch nie besucht.--Virtualone 01:23, 18. Nov 2004 (CET)

Ja, das mit den Abbruchbedingungen bei unzusammenhängenden Graphen (im ungerichteten Fall) und nicht stark-zusammenhängenden Graphen (im gerichteten Fall) hätte ich auch noch als Problem gesehen. Das könnte man höchstens noch dadurch reparieren, dass man abbricht, wenn man als minimum nur "unendlich" findet. Ein anderes Problem sehe ich jetzt nicht. Aber dann ist es vermutlich doch besser, deine Variante zu nehmen, da man so nichts an länge im Alg. spart. Werde das gleich ändern... --Coma 01:58, 18. Nov 2004 (CET)

Nicht ganz klar

In dem Algorithmus werden in der Initialisierung alle d(u) für u in U auf unendlich gesetzt. Aber dan wird immer in Linie 6 gesucht nach ein u mit d(u) minimal. Was macht das für Sinn wann immer alle u in U eine unendliche Distanz d(u) haben?

Kan jemand mir (hier oder vielleicht im Artikel) das erklären? Ich versuche den Algorithmus zu verstehen, dafür ist dieser Artikel auch gemeint natürlich. Freundliche Grüsse, 84.84.73.66 15:06, 31. Dez 2005 (CET)

Kein Antwort, obwohl es ein bedeutender Fehler war. Jetzt habe ich die Situation schon repariert. 84.84.73.66 18:17, 3. Jan 2006 (CET)

Meiner Ansicht nach war die alte Version auch richtig. Zudem haben nach der Initialisierung nicht alle Knoten in U eine unendliche Distanz, sondern d(s) ist 0 und s ist ein Element von U zu Beginn (da zu Beginn U = V und s ein Element von V ist). --217.252.247.129 11:23, 21. Jan 2006 (CET)

Ich habe mir erlaubt, die alte, einfachere Version des Algorithmus wieder einzustellen. Wie Benutzer "217.252.247.129" bereits bemerkt hat, ist diese vollkommen korrekt. Die neue Version von Benutzer "84.84.73.66" funktioniert zwar ebenfalls, ist aber unnötig kompliziert. Sie bietet zwar - je nach Graph - kleine Performance-Vorteile dadurch, dass in der Menge M (nur) die als nächstes zu besuchenden Knoten gespeichert werden, was das Auswählen des nächsten Knotens mit minimalen Kantenkosten etwas erleichtert; solche Dinge sind aber Sache der Implementierung (und nicht des Algorithmus an sich) und mit einer geeigneten Datenstruktur zum Abspeichern der Mengen ebenso (teilweise noch besser) zu erreichen. --thth 08:01, 28. Mai 2006 (CEST)

Noch eine Frage zur Initialisierung

Wenn in Zeile 4 eine leere Liste erzeigt wird (M:= EMPTYSET) wie kann dann in Zeile 7 der Knoten entfernt werden (wie es weiter unten in "Grundlegende Konzepte und Verwandschaften" erklaert wird). Ich denke doch dass M:= M UNION {v} bedeuete, dass v in M aufgenommen wird, oder irre ich mich da??

Hast du den Abschnitt "Nicht ganz klar" in dieser Diskussion gelesen (die Antwort vom 21. Jan. stammt übrigens auch von mir)? Benutzer "84.84.13.66" hat den Pseudo-Code verändert, aber anscheind vergessen die Zeilenangaben im nachfolgenden Text zu korrigieren. Zudem leuchten mir die Änderungen nicht ein. In dieser älteren Version sollten die Zeilenangaben noch stimmen: http://de.wikipedia.org/w/index.php?title=Algorithmus_von_Dijkstra&oldid=11653579 --89.51.46.84 18:22, 15. Feb 2006 (CET)

Änderungen am eigentlichen Algorithmus

Danke erst einmal an denjenigen welcher meine Blindheit (und die damit einhergehenden Tippfehler beseitigt hat. Habe jedoch die Zeilen

09            u := expand(currentNode, G);
10            foreach v in A[u]  do { // Alle Nachbarknoten von v
11               // relaxiere alle Nachfolger

wieder in

09            sucessors := expand(currentNode, G);
10            forall v in sucessors do { // Alle Nachbarknoten von v
11               // relaxiere alle Nachfolger

umgewandelt, da man für A[u] erst einmnal erklären muss was eine Adjazenzliste oder was auch immer ist. Eine Menge von Knoten reicht meiner Meinung nach hier aus und spart unnötige Erklärungen. (da die zugrundeliegende Datenstruktur für die Idee egal ist) Ansonsten sollte der Algorithmus so aber eigentlich in Ordnung sein. (aus Cormen übernommen und leicht modifiziert) Regnaron 12:27, 3. Jul 2006 (CEST)

Leider ist durch diese Rückänderung der "relax" Aufruf falsch:

09            sucessors := expand(currentNode, G);
10            forall v in sucessors do { // Alle Nachbarknoten von v
11               // relaxiere alle Nachfolger
12               relax(u, v, w);

Siehe relax Funktion: u ist der Knoten zu dem der Teilgraph den minimalen Weg hat. Dieser wird nicht definiert und auch nicht klar bestimmt aus der Menge sucessors.

Ich schlage dadurch folgende Änderung vor, da das bestehende unverständlich und meines Erachtens nicht korrekt ist.

09            u := expand(currentNode, G);
10            foreach v in A[u]  do { // Alle Nachbarknoten von v
11               // relaxiere alle Nachfolger
12               relax(u, v, w);

193.170.132.217 12:59, 3. Jul 2006 (CEST)

Autsch, du hast absolut recht! Das kommt davon wenn man einigen Variablen sinnvolle Namen geben will, und das dann nicht überall konsequent durchzieht. Ich habe es gerade nochmal geändert und hoffe dass jetzt alles wieder korrekt sein sollte. Kannst du vielleicht nochmal drübergucken? Scheine was das angeht echt ein bisschen betriebsblind zu sein :-) Regnaron 06:24, 5. Jul 2006 (CEST)

Das einzige Problem was ich noch sehe ist, dass sucessor (u) keine saubere Implementierung ist. Angenommen successor() gibt den Nachbarknoten aus, dann wird in der forall ein Nachfolger ausgegeben, und im relax() Aufruf der nächste! Also müsste successor() bei jedem zweitem Mal den nächsten Knoten ausgeben, was ansich nicht wirklich von einer sauberen Lösung zeigt. Speichere einfach den Knoten zwischen und das passiert nicht. Wenn du unbedingt forall haben willst würde das in etwa so aussehen:

10            forall v := sucessors(u) do {
11               // relaxiere die Kante zwischen u und seinem Nachfolger
12               relax(u, v, w);

Auf jeden Fall besser - wie nach der Richtlinie die du oben verwendet hast. z.B: G für Graph, Q für Pr. Warteschlange (und wie wir es in der Vorlesung gelernt haben) - wäre (foreach oder forall ist egal)

10            foreach v := A [u] do {  // A: Adjacents = Menge der Nachbarn eines Knotens
11               // relaxiere die Kante zwischen u und seinem Nachfolger
12               relax(u, v, w);

193.170.133.241 11:01, 5. Jul 2006 (CEST)

Hi mal wieder!

Ich habe mal deinen ersten Vorschlag übernommen, da sucessors meiner Meinung nach schlicht und ergreifend mehr sagt als A. (wenn der leser ein bisschen Englisch kann, wird er merken dass sucessors wahrscheinlich alle Nachfolger zurückliefert) Habe dazu noch den Kommentar darüber etwas verändert um das ganze nochmal zu zeigen dass es sich bei sucessors um die Nachfolger handelt. Bezüglich foreach und forall hast du komplett recht dass es Jacke wie Hose ist was man nun schreibt. :-) Aber wieso meinst du dass foreach v := A [u] besser wäre als forall v := sucessors(u)? Ist doch exakt dasselbe? Ob ich die Funktion nun A oder sucessors nenne macht doch keinen Unterschied? Beides ist eine Funktion angwendet auf ein Arguement (in diesem Falle u) welche eine Menge von Knoten zurückliefert. (Außer das A halt auf die Adjazenzliste die man verwenden kann anspielt, und sucessors halt darauf dass es sich um Nachfolger handelt) Regnaron 17:56, 5. Jul 2006 (CEST)

Fehler in den Grafiken

Würzburg wird vor Erfurt besucht, was falsch ist, das die Kante Kassel-Erfurt < Frankfut-Würzburg. Leider bin ich zu unerfahren um dies auszubessern.

Hi, die Karte ist schon richtig. Es stimmt zwar, dass die Kante Kassel-Erfurt < Frankfurt-Würzburg ist, aber du startest in Frankfurt, und musst erst einmal nach Kassel kommen. Somit müsstest du die Kante Frankfurt-Kassel-Erfurt und die Kante Frankfurt-Würzburg vergleichen. Die erste Kante hat kosten von 173+137 = 310 > 217 = Frankfurt-Würzburg Regnaron 13:38, 3. Jul 2006 (CEST)

Nachtrag: Aber danke für den Hinweis, ich sehe gerade, dass die Kante Kassel-Erfurt eigentlich gar nicht in dem Graphen sein sollte :-D Regnaron 13:45, 3. Jul 2006 (CEST)

Das Problem war, dass man in Kassel schon war, deshalb wars falsch. Lob für die schnelle Ausbesserung. 193.170.133.241 23:35, 4. Jul 2006 (CEST)

Die Grafiken haben Schreibfehler! -Mannheim und Manheim -Aufgsburg und Augsburg

Dijkstra <-> A*

"...dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in..." Eigentlich dient der Algorithmus zur Lösung des single-source shortest-paths problems, d.h. der Berechnung des kürzesten Pfades zwischen einem Startknoten und allen Knoten. Hier wird die Abarbeitung nur beim Erreichen des Zielknotens abgebrochen --MarcoBe 11:05, 9. Nov. 2006 (CET)

Ist der Dijkstra nicht eigentlich eine spezialisierte version von der A* suche mit entsprechender heuristik? wenn nicht, sehe ich in dem artikel nicht, wie er sich davon unterscheided, wenn ja sollte das im artikel genannt werden.

Ja und nein. Beide Algorithmen sind quasi gleich, stimmt. Dijkstra = A* mit Heuristik h(v) = 0 für alle Knoten v, bzw A* = Dijkstra + Heuristik. Dijkstra kann man aber auch verwenden wenn man die kürzesten Pfade zu allen Knoten finden will. Dies kannst du mit dem A* quasi nicht, da es sinnlos ist eine Heuristik zu verwenden um nicht alle Knoten explorieren zu müssen wenn du eh alle kürzesten Pfade zu allen Knoten finden willst :-) Aber man kann, wenn man will, eben mit Dijkstra auch nur nach einem Knoten suchen und abbrechen sobald man ihn gefunden hat) --Regnaron 21:11, 9. Nov. 2006 (CET)

Für mich wäre das Finden eines kürzesten Weges zwischen zwei Knoten ein Spezialfall des Algorithmus - und in der Ergebnismenge stehen ja auch die kürzesten Abstände zu den bereits betrachteten Knoten drin. Das steht ja auch im Text so drin, aber es gibt halt einen Unterschied zwischen single-pair shortest-path und single-source shortest-paths und das gibt der einleitende Satz nicht her. --MarcoBe 10:52, 10. Nov. 2006 (CET)

Zeitkomplexität

Die Formel fuer den Aufwand ist falsch, nicht O(m+n*log(n)) sondern O((m+n)*log(n)) ist korrekt.

Wie kommst du denn darauf? Wäre schön, wenn du das mal erklären würdest.--MarcoBe 11:08, 9. Nov. 2006 (CET)

Stimmt MarcoBe zu. Die Formel O(m+nlog(n)) ist (unter zuhilfenahme von Fibonacci Heaps) korrekt. Diese können das DecreaseKey welches beim relaxieren der Kanten verwendet wird in amortisiert Konstanter Zeit machen. (Diese Art von Anwendung war glaube ich sogar ein Grund warum Fibonacci Heaps entwickelt wurden) --Regnaron 21:11, 9. Nov. 2006 (CET)

Ich weiß jetzt, wie er/sie darauf gekommen ist. Die Formel O((m+n)*log(n)) ist richtig, wenn man die priority-queue als Heap implementiert. Dann ergibt sich nämlich O(n*(1+logn+logn+logn)+m*logn), da der Aufwand für jede Funktion (insert (Einfügen eines Elementes), remove (Entfernen eines Elementes), extractMin (Rückgabe und Entfernen des Elementes mit höchster Priorität), changePriority (Ändern der Priorität eines Elementes - in diesem Fall (logn) ist. Nur falls es jemanden interessiert...--MarcoBe 14:59, 10. Nov. 2006 (CET)

Ich finde es unschön die Zeitkomplexität in Abhängigkeit zur Implementierung anzugeben. Ohne Beschränkung der Allgemeinheit ist die Laufzeit O(n²), da |E| durch O(|V|²) beschränkt ist. Nur bei dünn besetzten Graphen für die gilt, daß |E| durch k*|V| beschränkt ist, macht die Verwendung von Fib.-Heaps Sinn und verdient eine eigene Betrachtung. ~~

Vorschlag zum Löschen

{{Löschen}}

Die Graphentheorie kann, zumindest entsprechend der vorherrschenden Meinung, nicht als Teilgebiet der Mathematik betrachtet werden. Ich schlage daher alle Artikel (inklusive Diskussion) über diese völlig sinnfreie Pseudowissenschaft zum Löschen vor.

 Pro Ich habe gerade hier nochmals genauer nachgelesen. Obgleich eine Viezahl von Teilgebieten und Anwendungen der Mathematik aufgelistet sind, fehlt die Graphentheorie.

 Kontra Das kann doch nur ein Scherz, oder? Die Graphentheorie, ob nun Teilgebiet der Mathematik oder nicht, hat viele konkrete Anwendungen in der Realität und gerade Dijkstras Algorithmus ist in der Informatik von großer Bedeutung. Ich mache den Gegenvorschlag, diesen völlig sinnfreien Pseudo-Löschwunsch zu entfernen.

 Kontra Wenn etwas irgendwo nicht steht, heißt es nicht zwingend, dass es auch nicht so ist. Zur Abwechslung kann man auch hier schauen, und zwar reicht da schon der erste Satz. Also im Netz sind schon einige Scherzkekse unterwegs... --Sixot 01:35, 24. Feb. 2007 (CET)

Natürlich ist die Graphentheorie ein Teilgebiet der Mathematik. Bob.v.R 02:05, 23. Feb. 2007 (CET)

Beispiel

Also da es bei dem Algorithmus darum geht, einen Baum zu ermitteln, find ich es sehr fragwürdig, in dem Beispiel die Kanten, die benutzt wurden, um zu den markierten Knoten zu kommen, nicht zu markieren. Da geht der ganze Sinn des Beispiels meiner Meinung nach flöten! --Sixot 14:18, 31. Jan. 2007 (CET)

ja, und man sieht so am Ende überhaupt nicht, welcher Weg zu einem Knoten nun wirklich der kürzeste ist, da nur die Knoten, aber nicht die Kanten markiert sind. --Fischbuerger 17:13, 21. Feb. 2007 (CET)

Frage zu negativen Kantengewichten

Illustriertes Gegenbeispiel, warum negative Kantengewichte nicht zulässig sind: Startend in Knoten eins, wird Dijkstra im ersten Schritt d(zwei)=1 und d(vier)=4 setzen, d(zwei) ist am kleinsten, folglich wird im nächsten Schritt d(drei)=2 gesetzt. d(drei) ist kleiner als d(vier), hat aber keine weiteren Nachbarn. Folglich wird Knoten vier als letztes betrachtet und damit niemals die negative Kante (4,3), da Dijkstra zuvor abbricht. --Chin tin tin 22:33, 11. Aug. 2008 (CEST)

Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ sein.

Und wieso nicht? Kann vielleicht jemand den Artikel um ein illustriertes Gegenbeispiel erweitern, warum negative Kantengewichte nicht zulässig sind? --160.45.45.225 13:55, 15. Feb. 2007 (CET)

In der Tat ist es so, dass der Algorithmus auch für negative Kantengewichte funktioniert. Die einzige Einschränkung ist, dass es keine negativen Zyklen geben darf. Die Behauptung, der Algorithmus funktioniere nur für positive Gewichte ist einfach falsch.

Nein, der Algorithmus nimmt immer die nächste kürzeste Kante auf. Er basiert auf der Idee, dass ein Weg durch weitere Kanten nicht mehr kürzer werden kann. Bei negativen Kantengewichten gilt das nicht mehr. Ein Beispiel: Knoten {a, b, c}, Kanten {(a,b,-10),(a,c,1),(b,c,5)}, Start-/Zielknoten ist c. Von c aus würde zunächst die Kante (a,c) mit Länge 1 verwendet. Der kürzeste Weg von a nach c hätte also die Länge 1. Danach würde (b,c) gefolgt. Die Kannte (a,b) würde gar nicht mehr betrachtet, und selbst wenn man das täte, könnte man bereits berechnete Wege nicht mehr korrigieren. Benötigt man negative Kanten, muss man zu anderen Algorithmen wie Bellmand-Ford greifen. Bei negative Zyklen kann man kürzeste Wege erst gar nicht richtig definieren, daher funktioniert da erstmal kein Algorithmus. -- daniel

Das stimmt, aber ich finde auch, dass das im Artikel an einem Beispiel erklärt werden sollte. --Daniel Mex 16:44, 2. Jul. 2007 (CEST)

Mit einer kleinen Änderung funktioniert der Algorithmus auch für negative Kanten (aber natürlich mit der Einschränkung dass es keine negativen Zyklen geben darf). Man muss nur beim Punkt 2.2 des informellen Algorithmus das "noch unbesuchten" entfernen bzw. im Pseudocode die Bedingung "if !(z € X)" entfernen. Der Satz "Ist man dagegen nur an dem Weg zu einem ganz bestimmten Knoten interessiert, so kann man in Schritt (2) schon abbrechen, wenn der gesuchte Knoten der aktive ist." gilt dann allerdings nicht mehr. Wobei man soviel ich weiß den Dijkstra sowieso nicht benutzen sollte um den Abstand zu einem bestimmten Knoten zu ermitteln. --Popelmaus 16:29, 25. Jul. 2009 (CEST)

Beschreibung zu implementierungsnah

Hallo,

ich habe mir gerade mal diesen Artikel angesehen und empfinde insbesondere die initiale Beschreibung des Algorithmus als zu implementierungsnah. Das Grundprinzip des Dijkstra-Algorithmus geht dabei m.E. verloren bzw. wird vom Lernenden gar nicht erst verstanden. Insbesondere die Einführung der priority queue und des Spannbaums würde ich mir für die allgemeine Beschreibung des Algorithmus eher sparen, da sie nicht zur grundlegenden Funktionsweise selbst gehören.

Aus meiner Sicht bilden folgende Schritte den Kern des Dijkstra-Algorithmus:

1. Initialisierung aller Knoten mit der Distanz "unendlich", die des Startknotens mit 0.
2. Markierung der Distanz des Startknotens als permanent, alle anderen Distanzen als temporär.
3. Setze Startknoten als aktiv.
4. Berechne die temporären Distanzen aller Nachbarknoten des aktiven Knotens durch Addition von dessen Distanz mit den Kantengewichten.
5. Wenn eine solche berechnete Distanz für einen Knoten kleiner ist als die aktuelle, aktualisiere die Distanz und setze den aktuellen Knoten als Vorgänger. (Update, die zentrale Idee des Dijkstra-Algorithmus!)
6. Wähle einen Knoten mit minimaler temporärer Distanz als aktiv. Markiere seine Distanz als permanent.
7. Wiederhole 4-7, bis es keinen Knoten mit permanenter Distanz gibt, dessen Nachbarn noch temporäre Distanzen haben.

Ich würde einen neuen Absatz "Grundidee" erstellen, in welchem diese allgemeinen Schritte beschrieben werden. Darin sollte insbesondere der Update-Schritt erläutert werden. Die Motivation für den Update kann sehr schön über das Fehlschlagen des Breitensuche-Algorithmus bei gewichteten Graphen erläutert werden, denn genau dieses Fehlschlagen macht den Update der Distanzen notwendig. Die Verwendung einer Priority Queue ist einfach nur ein vereinfachendes Hilfsmittel bei der Implementierung, aber keineswegs zentral für den Algorithmus. Es verdeckt hier eher die Grundidee und sollte daher in einem spezielleren Absatz beschrieben sein.

Vielen Dank für Rückmeldungen --Mkleine 21:29, 30. Jun. 2007 (CEST)

Mir haben deine Schritte besser geholfen als der Artikel. Im Artikel wird der Algorithmus durch Pseudocode beschrieben, was nicht eingängig ist. Das ausführliche Beispiel danach bringt nur etwas, wenn man die exakten Schritte des Algorithmus zuvor verstanden hat, die aber nur durch den Pseudocode erklärt werden. Daher kann ich dir nur zustimmen! --Agent00 20:54, 25. Sep. 2007 (CEST)

Ich stimme dir voll und ganz zu. Der Algorithmus, der momentan im Artikel steht, ist weitestgehend ungeeignet, um daran die Arbeit des Dijkstra-Algorithmus zu verstehen. Ich bin kein Informatiker, und arbeite auch nicht aktiv an der Wiki mit, aber das hindert mich ja nicht daran, einen Verbesserungsvorschlag zu unterbeiten:

• Bisherigen Quelltext durch vereinfachten, allgemeineren Pseudocode ersetzen.
• Den bisherigen Quelltext komplett ausarbeiten (ist ja im Endeffekt fast lauffähiger C-Code), und über Wiki-Source verfügbar machen (und natürlich verlinken)
• Falls irgendwer von euch aktiven übermäßig viel Zeit hat, kann er ja allen Programmieranfängern einen gigantischen Gefallen tun, und eine Animation erstellen, die Anhand der Position im Quelltext und einem anschaulichen Beispiel (z.B. das aus dem Artikel) 'Zeile für Zeile' den Algorithmus verdeutlicht.

Aber wer bin ich, euch vorschläge zu machen? Danke für alle Arbeit, die ihr schon in die Wiki gesteckt habt. --89.244.198.92 14:09, 11. Mai 2008 (CEST)

Informeller, formeller Algorithmus und Pseudocode

Ich hab mal den Artikel entsprechend erweitert. Den Pseudocode habe ich größtenteils aus dem niederländischen Wiki übernommen. Ich finde diese Trennung besser verständlich als einfach nur eine halbfertige Implementierung. --Zhujik 13:23, 20. Jul. 2008 (CEST)

Ich finde es auch ziemlich unschoen da Implementierung in C hinzuschreiben und man bekommt doch nur wieder Pseudocode zu sehen. Ok, die Syntax sieht mehr nach C aus als die des anderen Pseucodes, aber es gleich C zu nennen, ich weiss nicht... --*skomp 11:45, 2. Aug. 2008 (CEST)

Ich finde der jetzige Pseudocode ist ein bisschen unübersichtlich... Ich finde den aus dem englischen Wiki deutlich besser und einfacher zu verstehen. Daher mein Vorschlag den englischen Pseudocode zu nutzen oder den jetzigen besser zu erläutern. --Nel1988 09:25, 19. Nov. 2008 (CET)

Beispiel Grafik nachbessern

Die Kante zum Knoten "Stuttgart" überdeckt die 1 des Kantenlabels "183km". Falls jemand etwas zu tun sucht: das könnte nachgebessert werden ;) Die Bilder sind als .svg gespeichert und Bearbeitung ist verlustfrei möglich. Grüße, --Sulai 13:42, 2. Aug. 2008 (CEST)

Ich habe mal Step3 editiert, da der original Ersteller es wohl nicht mehr macht. Wenn das so gefällt, mache ich das mit den anderen auch so. Ich habe auf UTF-8 umgestellt und die „oo“ durch „∞“ ersetzt. Da ich keine „Times“ Schriftart habe, habe ich „DejaVu Serif“ genommen. Wenn was serifenloses erwünscht wird, würde ich „DejaVu Sans“ nehmen. Nun habe ich natürlich keine Ahnung, wie das in anderen Browsern und anderen Betriebssystemen aussieht. Ich bitte um Kritik. Wenn ihr das so wollt, sagt es hier. Da ich jede Datei mit inkscape anfasse (graphviz hat seine Grenzen), kann ich noch andere Sachen ändern. Vielleicht hat jemand eine Idee den Vorgänger mit einzutragen in jeden Knoten. Mir fiel nur keine intuitive Lösung ein.

(nicht signierter Beitrag von Faron (Diskussion | Beiträge) 20:42, 30. Mai 2009 (CEST))

Optimierung des Dijkstra Algorithmus

Komischerweise ist das rekursive Abschneiden von "Wegstücken, welche mit dem Start und dem Ziel über gleiche Teilstrecken verbunden sind" hier nicht erwähnt. Wenn ich den Algorithmus richtig verstanden habe, könnte man ihn auf diese Weise doch optimieren, da sich dadurch die Prüfmenge verkleinert? Im konkreten Fall würde also Erfurt und Stuttgart erst einmal aussortiert, bevor der Algorithmus sie überflüssigerweise untersucht.

Weiter liessen sich dann alle Wegvarianten aussortieren, welche länger sind als andere, was eigentlich dazu führen würde, dass man den Algorithmus sozusagen umgekehrt entwickelt hat. Eine dezentrale UND ausschliessende Methode wird sehr wahrscheinlich aber langsamer als der normale Dijkstra Algorithmus (Wobei mir da der Kruskal Algorithmus auf alle negativen Distanzen einfällt)... (nicht signierter Beitrag von 92.105.162.226 (Diskussion | Beiträge) 02:02, 1. Mai 2009 (CEST))

Stop, wenn alle besucht: Falsch!

In der informellen Beschreibung steht, dass der Algorithmus stoppt, wenn alle Knoten besucht wurden. Das stimmt jedoch nicht. Der Algorithmus stoppt, wenn das Ziel an der Reihe ist und zu diesem Zeitpunkt können auch Knoten unbesucht sein. Beispiel: (Adjazenzmatrix, man will von 0 nach 1)

	0	1	2
0	-	1	5
1	1	-	6
2	5	6	-

Natürlich wird die 1 besucht und es ist Ende. Das gibt es auch bei komplexeren Graphen. --Chricho 19:27, 25. Mai 2009 (CEST)

In der Variante, die dort steht, findet der Algorithmus kürzeste Wege ausgehend vom Startknoten zu allen anderen Knoten. Dafür muss er natürlich alle durchlaufen. Um den Weg zu einem speziellen Knoten zu finden kann man natürlich vorher abbrechen, das stimmt. Baue ich mal ergänzend ein. -- Pberndt _(DS) 20:09, 25. Mai 2009 (CEST)

Beispiel (2)

Entschuldigung, ich spreche Deutsch nur ein wenig. Aber es gibt Problems mit dem Beispiel.

• Mannheim (step01) oder Manheim (step02)?
• Augsburg (step01) oder Aufgsburg (step03) ?

Die Verbindungen zwischen Städten sind überraschend: in meiner Landkarte ist Stuttgart zwischen Karlsruhe und Augsburg. Ich lese auch :

• Würzburg - Frankfurt = 120 km (nicht 217 km)
• Karlsruhe - Augsburg = 220 km (nicht 250 km)
• Nürnberg - Stuttgart = 208 km (nicht 185 km)
• und so weiter

Der Beispiel ist mathematisch korrekt, aber nicht realistisch fr:user:HB - 1/07/2009 (nicht signierter Beitrag von 82.67.217.175 (Diskussion | Beiträge) 16:01, 1. Jul 2009 (CEST))

Dijkstra ist kein Greedy-Algorithmus

Da der folgende Absatz (im Abschnitt Grundlegende Konzepte und Verwandtschaften) falsch ist, habe ich ihn soeben ersatzlos gelöscht:

Der Algorithmus gehört zur Klasse der Greedy-Algorithmen. Sukzessive wird der nächstbeste Knoten, der den kürzesten Abstand zum Startknoten besitzt (Zeile 04), untersucht und dann aus der Menge der noch zu bearbeitenden Knoten entfernt. Damit findet sich eine Verwandtschaft zur Breitensuche, die ebenfalls solch ein gieriges Verhalten aufweist.

Unter Greedy-Algorithmus findet sich dagegen folgendes:

Sie zeichnen sich dadurch aus, dass sie schrittweise denjenigen Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis verspricht.

Gierig heißt soviel wie nimm zu jedem Zeitpunkt soviel wie du kriegen kannst. Demzufolge sind Dijkstra und Breitensuche überhaupt nicht gierig, da die geschätzten Restkosten bis zum Ziel überhaupt nicht beachtet werden. Beide Algorithmen wissen also gar nicht, welcher Folgezustand den größtmöglichen Gewinn verspricht und können daher auch nicht gierig sein.

Die korrekte Beschreibung für einen Greedy-Algorithmus wäre also

Sukzessive wird der nächstbeste Knoten, der den kürzesten Abstand zum Zielknoten (nicht Startknoten!) besitzt, untersucht [...]

Aber das entspricht nicht dem Verhalten von Dijkstra. --Sargeras 12:25, 29. Jan. 2008 (CET)

Ob vorwärts oder rückwärts ist egal. Der Algorithmus denkt jeweils nur einen Schritt voraus. Und das ist IMHO das Wesen des Greedy-Algorithmus. Wenn man die Aufgabe folgendermaßen formuliert passt es: Suche von einem Knoten ausgehend den jeweils kürzesten Weg zu jedem anderen Knoten.--Suricata 12:52, 29. Jan. 2008 (CET)

Ich verstehe leider nicht was du meinst. Ich zitiere nochmal aus Greedy-Algorithmus: Greedy-Algorithmen sind meist schnell, lösen viele Probleme aber nicht optimal. Wie passt das zu Dijkstra? Der ist langsam und löst das Problem immer optimal.

Leider ist der Artikel zu Greedy-Algorithmus sehr allgemein gehalten und enthält kein anschauliches Beispiel. Hier [1] gibts ein Java-Applet, das auch einen Greedy-Algorithmus veranschaulicht. So wie die Algorithmen in diesem Applet dargestellt werden, stehen sie auch in meinem Künstliche Intelligenz – Ein moderner Ansatz Buch drin.

Ich hab mir nun mal den Greedy-Algorithmus Artikel komplett durchgelesen, und versucht ihn zu verstehen. Auch dort wird Dijkstra als gierig klassifiziert. Ich diskutiere erst mal dort weiter, um herauszufinden, was überhaupt ein Greedy-Algorithmus ist... --Sargeras 01:20, 5. Feb. 2008 (CET)

Die Begründung, dass Disjksta nicht greedy ist, weil er optimal ist, ist defitiv falsch. Es gibt genügend Probleme, für die Greedy-Algorithmen durchaus optimale Lösungen liefern. Und die Geschwindigkeit eines Algorithmus kann durch Zusatzaufwand immer beliebig verlängert werden.

Wie dem auch sei...Der Dijkstra-Algorithmus handelt meiner Meinung nach aber definitiv gierig bei der Auswahl des nächsten Knotens, welcher aus der Queue entfernt wird. --Gero, 16:10, 5. Feb. 2008 (CET)

Nur weil er die beste Möglichkeit auswählt, handelt er nicht gierig. Warum sollte ein Algorithmus nicht die beste Möglichkeit auswählen? Mit der Begründung ist praktisch jeder Algorithmus gierig. Ich habe eine Gegenüberstellung von A*, Dijkstra und einem Greedy-Algorithmus erstellt, die mein Verständnis eines Greedy-Algorithmus aufzeigen soll. --Sargeras 18:33, 5. Feb. 2008 (CET)

Wenn ich das Konzept eines Greedy-Algorithmus richtig verstanden habe, dann müsste doch der Dijkstra-Algorithmus bei jeder Iteration nur den kürzesten Weg weiter verfolgen. Wenn also vom Startpunkt S drei Kanten abgehen, dann würd er ausschließlich den Weg verfolgen, der über die kürzesten Abstände zwischen den einzelnen Knoten verfügt. Greedy ist für mich eher ein Algorithmus zur diskreten Optimierung eines Entscheidungsbaums, bei dem die Kantengewichte Wahrscheinlichkeiten entsprechen (wo dem zufolge natürlich nicht addiert wird, sondern multipliziert). Denn dort macht es ja Sinn, in jedem Schritt den kürzesten Weg zu wählen. --89.244.198.92 14:20, 11. Mai 2008 (CEST)

Dijkstra ist definitiv greedy. Die Begründung will ich jetzt nicht weiter breittreten, aber in Cormen, Leiserson, Rivest, Stein, 2. englische Auflage, 2005, S. 596, "Introduction to algorithms" steht: "Because Dijkstra's algorithm always chooses the "lightest" or "closest" vertex in V - S [Anmerkung: Menge unbesuchter Knoten], we say, that it uses a greedy strategy." S. 370: "A greedy algorithm alway makes the choice that looks best at the moment." Dass Dijkstra optimale Lösungen findet, ist kein Beweis dafür, dass er nicht greedy ist. Klassischer Fall von Implikation. Die gilt halt nunmal nicht rückwärts. -- 92.75.196.156 22:34, 24. Aug. 2009 (CEST)

C-Implementierung herausnehmen

Mittlerweile finde ich, dass der C-Code deplaziert ist. Er trägt nicht zum verständnis bei, und für jemanden, der eine Implementierung schreiben muss, reicht der Pseudocode. Von daher sollte der Punkt rausgenommen werden. --Zhujik 11:59, 12. Aug. 2008 (CEST)

Ich bin deiner Meinung und habe den Code gelöscht. --Stefan Birkner 13:33, 12. Aug. 2008 (CEST)

Ich finde die C-Implemetierung schon hilfreich. Der Pseudocode ist zuteilen sehr mathematisch formuliert, was eine Hürde für den ein oder anderen sein kann. Mengentheorie und Aussagenlogik sind für uns irgendwo ganz unten bei den Grundlagen angesiedelt, dies muss jedoch nicht auch für unstudierte gelten, die genauso Nutzer der Wikipedia sind und damit diesen Pseudocode kaum nachvollziehen können. Ich habe nicht den nötigen Überblick über die Wikipedia. Gibt es vielleicht eine Möglichkeit Code aus dem Artikel auszulagern und darauf zu verweisen (also eine Art Code-Wiki)? --78.50.243.16 10:02, 19. Mär. 2009 (CET)

Das gibt es! Ist unten verlinkt, da ist bisher nur meine Pythonversion. Erweiterungen willkommen. -- Pberndt _(DS) 00:11, 5. Sep. 2009 (CEST)

Algorithmus in Pseudocode

In Pseudocode sieht der Algorithmus wie folgt aus:

 foreach v $\in$ V(G) do d(v) = $\infty$
 ;
 A := $g_{b}$
 d(a) := 0
 X := $\emptyset$
 foreach z : z $\in$ $M_{(g_{b})}$ do 
   X := X $\cup$ {z}
   d(z) := gew($g_{b}$,z)
 ; 
   /*
    * X und d sind jetzt initialisiert
    */
 while not(X = $\emptyset$) do
   /*
    * X ist noch nicht leer
    */
   y : (y $\in$ X) $\land$ (d(y) = MIN {d(y)'|y' $\in$ X}
   /*
    * y ist daher das Element von x mit dem kleinstene Wert von d(v) --
    * das ist der endgültige Wert von d(y)
    */
   A := A $\cup$ {y}
   X := X$\setminus${y} 
   /*
    * y ist jetzt verschoben von X nach A
    */
   foreach z: z $\in$ M_(y) $\land$ not (z $\in$ A) do 
     if not (z $\in$ X) then
        X := X $\cup$ {z} 
        d(z) := d(y) + gew(y,z)
     else 
    /*
     * somit ist z $\in$ X
     */ 
        d(z) := MIN{d(z), d(y) + gew(y,z)}

ich habe das mal im Beitrag etwas konsequenter durchgezogen. Zwei Anmerkungen: 1. Der Algorithmus ermittelt die summierten Kantengewichte der kürzesten Pfade, aber nicht die Pfade selbst (soll heissen: nach Durchlauf des Algorithmus weiss ich zwar, wie weit es von Frankfurt nach München wenigstens ist, aber nicht, welcher Weg denn nun der kürzeste ist. Das wird im informellen Pseudocode ermittelt. Anpassung wäre leicht, mir aber jetzt rein Uhrzeitmäßig zu spät. 2. Das letzte if-Bedingung ist doch überflüssig, oder? {z} in jedem Fall mit X vereinigen und die Minimum-Funktion auf d(z) ansetzen. 85.179.117.16 23:25, 4. Sep. 2009 (CEST)

• Ist der Pseudocode der englischen Wikipedia nicht viel gelungener?

---

In the following algorithm, the code u := node in Q with smallest dist[], searches for the vertex u in the vertex set Q that has the least dist[u] value. That vertex is removed from the set Q and returned to the user. dist_between(u, v) calculates the length between the two neighbor-nodes u and v. alt on line 11 is the length of the path from the root node to the neighbor node v if it were to go through u. If this path is shorter than the current shortest path recorded for v, that current path is replaced with this alt path. The previous array is populated with a pointer to the "next-hop" node on the source graph to get the shortest route to the source.

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:           // Initializations
 3          dist[v] := infinity               // Unknown distance function from source to v
 4          previous[v] := undefined          // Previous node in optimal path from source
 5      dist[source] := 0                     // Distance from source to source
 6      Q := the set of all nodes in Graph    // All nodes in the graph are unoptimized - thus are in Q
 7      while Q is not empty:                 // The main loop
 8          u := vertex in Q with smallest dist[]
 9          remove u from Q
10          for each neighbor v of u:         // where v has not yet been removed from Q.
11              alt := dist[u] + dist_between(u, v)       // be careful in 1st step - dist[u] is infinity yet
12              if alt < dist[v]              // Relax (u,v,a)
13                  dist[v] := alt
14                  previous[v] := u
15      return previous[]

---

Könnte man doch einfach eindeutschen. --78.50.243.16 13:32, 19. Mär. 2009 (CET)

Der Meinung bin ich auch. Das hatte ich auch schon vor etwas längerer Zeit vorgeschlagen. (siehe ein paar Zeilen tiefer (oder Hier)). Aber scheinbar findet man in Diskussionen keine Gleichgesinnte.... Aber meine Unterstützung hast du! --Nel1988 13:52, 19. Mär. 2009 (CET)

dann ändere es doch, hindert dich ja keiner dran. --Zhujik 20:31, 19. Mär. 2009 (CET)

Zuhjik, ich bin mir nicht sicher, ob es immer eine gute Idee ist, einfach mal schnell seine Ideen in ein Wiki zu hacken, wenn es ggf. plausible Argumente dagegen geben kann. --92.226.145.61 14:22, 20. Mär. 2009 (CET)

Eben, daher lieber erstmal hier den Vorschlag machen und auf Antworten warten... --Nel1988 12:49, 21. Mär. 2009 (CET)

nunja, der Diskussionsbeitrag stand ja jetzt auch schon ein bisschen länger da. man kann ja auch immernoch die alte version laden... :) --Zhujik 21:13, 21. Mär. 2009 (CET)

ich habe den formellen Pseudocode etwas konsequenter gestaltet. Finde ihn aber prinzipiell nicht sonderlich hilfreich, da zuviele mathematische Formelsymbole. Mag für Graphentheoretiker normal sein, aber selbst als diplomierter Informatiker musste ich mich erstmal in den Mathe-Modus versetzen, um das zu verstehen und nachzuvollziehen. Votiere hiermit für den informellen Pseudocode aus der englischen version 85.179.117.16 23:25, 4. Sep. 2009 (CEST)

Die Konsequenz fehlte da tatsächlich irgendwie o_O Finde ihn auch hinderlich. Der Sinn von Pseudocode ist mMn, dass Leser mit grundlegenden Programmierkenntnissen ihn verstehen, ohne vorher eine bestimmte Sprache gelernt haben zu müssen. Hier ist das Gegenteil der Fall - man muss die Notation der Mengenlehre kennen, um den Code zu verstehen. Außerdem kann man diese Mischung aus TeX und Monospace nur wiederlich schwer lesen. → Ändern! -- Pberndt _(DS) 00:08, 5. Sep. 2009 (CEST)

Da keine Reaktion kam: Erledigt. -- Pberndt _(DS) 16:58, 7. Sep. 2009 (CEST)

Kurzschrittalgorithmus

Der Kurzschrittalgorithmus, auch genannt Dijkstra-Algorithmus, ist ein Graph-Algorithmus der von Edsger Dijkstra in 1959 publiziert wurde. Für einen gerichteten Graphen $G$, bei dem der Abstand zwischen zwei beliebigen Knoten mindestens 0 beträgt, berechnet der Algorithmus für einen bestimmten Startknoten$g_{b}\in G$ den kürzesten Abstand zu allen Knoten von $G$. Dieser Algorithmus wird unter anderem angewandt bei Verkehrsmodellen, Routen-Navigationssystemen und in der Telekommunikation.

Dies Aussage zu Navigationssystemen ist so nicht ganz richtig. Hier findet eher der A* Algorithmus Anwendung. -- 134.155.99.71 19:59, 27. Nov. 2009 (CET)

Kontext

Den Algorithmus ausführlich zu erklären ist gut und wichtig. Was noch fehlt ist Kontext: Wie ist er entstanden, wo und wann zum ersten Mal publiziert? Tieferer Vergleich mit ähnlichen Algorithmen. (nicht signierter Beitrag von 213.23.196.74 (Diskussion | Beiträge) 10:09, 26. Nov. 2009 (CET))

Städtenamen in den Bildern falsch

In den Bilder sind die Städte Augsburg und Mannheim falsch geschrieben, kommt nicht so gut. 10:55, 14. Jan. 2010 (CET) (ohne Benutzername signierter Beitrag von 137.250.169.174 (Diskussion | Beiträge) )

unverständliche Formulierung in der Einleitung

..., wenn ein Pfad zwischen Startknoten und diesen Knoten nicht existiert, dieser aber in der Knotenmenge selbst vorliegt.

ist unverständlich. Wie kann ein Pfad erst nicht existieren und dann doch. Entweder die Knotenmenge des Pfades liegt in Knotenmenge des Graphs UND alle Kanten des Graphes liegen in der Kantenmenge des Graphs, oder es ist halt kein Pfad. Oder was ist gemeint?--Schönen Gruß "Wohingenau" 15:12, 4. Apr. 2010 (CEST)

Wohl ein Typo: Nicht der Pfad liegt in der Knotenmenge (sowas geht gar nicht), sondern die Knoten, zu denen kein Pfad existiert, liegen in der Knotenmenge. --Zahnradzacken 18:00, 5. Apr. 2010 (CEST)

'relax' nicht definiert oder verlinkt

Die Funktion(?) im Beispiel ist nicht definiert.--Schönen Gruß "Wohingenau" 17:25, 4. Apr. 2010 (CEST)

Im Beispiel ist noch mehr nicht definiert: Prioritätswarteschlange, Neusortieren, reconstructShortestPath(). Die Begriffe basieren auf einer früheren Version des Artikels. Auch der Abschnitt Zeitkomplexität bezieht sich noch auf frühere Zeilennummern und einen anderen Code (aber Komplexitätsanalyse anhand von Zeilen im Pseudocode ist eigenlich Unsinn). Für ein erstes Verständnis füge ich in den Artikel ein, dass es eine andere Bezeichnung für den Update-Schritt ist. Längerfristig braucht der ganze Artikel eine Menge an Arbeit. --Zahnradzacken 18:17, 5. Apr. 2010 (CEST)

Algorithmus in Pseudocode

An der Stelle bitte ich um Erläuterung zum Baustein: Was (welche Funktion) erfordert da eine Erklärung? Die Formulierung bei uns beschreibt doch umgangssprachlich, was zu tun ist, statt Funktionsnamen zu verwenden?! -- Pberndt _(DS) 20:56, 4. Apr. 2010 (CEST)

Hast du dir den engl. Artikel angesehn? Einfach die Erläuterung aus der engl. WP übersetzen.Was passiert bei 'Knoten in Q mit kleinstem Wert in abstand[]', u wird gelöscht,... Was passiert bei abstand_zwischen(u, v) insbesondere wenn ein Wert unendlich ist. Nur weil dir klar ist, heißt es ja nicht dass man es nicht ruhig erklären kann. Ohne die Erklärung erschwert es nur unnötig das Verständnis. Ich mach dass auch selber irgendwann aber hab grad keine Zeit für.--Schönen Gruß "Wohingenau" 21:25, 4. Apr. 2010 (CEST)

Ja, auch dort finde ich die Erklärung ziemlich übertrieben. Wie der Algorithmus selbst funktioniert, ist weiter oben erklärt. Erklärungen à la „abstand_zwischen(a,b) bestimmt den Abstand zwischen a und b. Und wenn es keinen Weg oder keinen mit einer endlichen Länge gibt, gibt es ∞ zurück.“ unterstellen dem Leser einen Mangel an Fähigkeit zum Mitdenken, der wohl kaum bei jemandem vorhanden sein wird, der einen Artikel über den Dijkstra-Algorithmus ließt. Wiedemauchsei – schaden tut's natürlich auch niemandem, wenn da noch etwas zu steht. -- Pberndt _(DS) 15:38, 5. Apr. 2010 (CEST)

Mitdenken kann manchmal schief gehen, weil implizite Annahmen nicht immer zutreffen. Deshalb ist es gut, wenn man möglichst genau die Absicht beschreibt. Darüber hinaus wurde das "Mitdenken" schon abgenommen, indem fast neben jeder Zeile Kommentare standen. Ich habe das als Fließtext vor den Code verschoben, damit man nicht zweispaltig lesen muss (links Code, rechts Kommentar). Außerdem habe ich den Pseudocode etwas eingedeutscht (schließlich gibt es da keine Schlüsselwörter) und ein bisschen aufgeteilt, damit man die Methodik besser erkennt. Die Abfrage auf Nichterreichbarkeit habe ich entfernt, da sie an der Korrektheit des Vorgehens nichts ändert, nur an der Anzahl der Durchläufe. Den Lückenhaftbaustein habe ich entfernt; falls das zu voreilig war, ruhig wieder einfügen. --Zahnradzacken 18:08, 5. Apr. 2010 (CEST)

negative Kantengewichte

Ich fände es angemessen, kurz darauf einzugehen, weshalb der Algorithmus nur für nicht-negative Gewichte funktioniert. Ich weiß zwar, dass dies so ist, und das kann ich hier auch nachlesen, aber weshalb ist mir nicht ganz klar. --89.204.153.5 15:45, 15. Mai 2010 (CEST)

MaNNheim

Mannheim bitte durchgehen im Beispiel mit 2 (!) n. (nicht signierter Beitrag von 188.99.36.179 (Diskussion) 20:13, 7. Aug. 2010 (CEST))

Zweiseitige Dijkstra-Algorithmus

Sollte der Zweiseitige Dijkstra-Algorithmus hier nciht auch erwähnt werden? Den Algorithmus um Forwärts und Rückwärtsschritte zu ergänzen sollte nach der grundlegenden Einführen nciht allzu schwer sein. Oder sollte dazu ein neuer Artikel erstellt werden? (nicht signierter Beitrag von Rapunzel77 (Diskussion | Beiträge) 09:45, 26. Aug. 2005 (CEST))

relax ohne decreaseKey?

Hallo, sollte nicht in der relax (u,v,w)-Routine erwähnt werden, daß mit dem Verändern der Distanz von v auch ein decreaseKey-Aufruf erfolgen muß, um die Priority Queue konsistent zu halten? Die aktuelle Beschreibung verführt dazu, diesen Schritt zu übergehen, und führt so zu falschen Ergebnissen. Insbesondere wird nur so verständlich, wieso die Queue bereits zu Beginn mit allen Vertices befüllt werden kann... (nicht signierter Beitrag von 134.96.194.50 (Diskussion | Beiträge) 14:13, 12. Okt. 2007 (CEST))

dead code?

im Djikstra Algorithmus selber wird Zeile

16 // Es konnte kein Pfad gefunden werden

wird doch nie erreicht. Weil g-Endknoten auch in der Q drin ist, und irgendwann u zugewiesen wird. Zeile 16 sagt dann was falsches aus. Grüsse, Daniel (nicht signierter Beitrag von 87.234.158.86 (Diskussion | Beiträge) 00:57, 15. Nov. 2007 (CET))

Syntax nicht klar definiert

Ich denke die Syntax dieses Codes ist nicht klar definiert.

Was ist π(n)? - runde Klammern. Ein Funktionszugriff? Wie ist diese Funktion definiert? Insbesondere werden dem Spannbaum π[v] Werte zugewiesen - wird hier ein Array bearbeitet? siehe relax: "π[v] := u;" (nicht signierter Beitrag von 80.133.40.97 (Diskussion | Beiträge) 20:46, 19. Dez. 2007 (CET))

Übersetzung aus dem Niederländischen

Hallo - ich fand die Erklärung in der niederländischen Wikipedia recht schön - vielleicht macht es ja Sinn, sie einzuarbeiten. Ich habe mich mal an einer Übersetzung versucht, bin aber nicht sicher, ob noch Dreher drin sind. (nicht signierter Beitrag von 85.181.180.135 (Diskussion | Beiträge) 16:32, 20. Jun. 2008 (CEST))

Grundlagen

Der Algorithmus basiert auf der Beobachtung, dass der Abstand (die Länge des kürzesten Pfada) zwischen zwei beliebigen Knoten v und w eines gerichteten Graphen $G$ wie folgt berechnet werden kann:

Sei $d(x)\!$ der Abstand zwischen v und x, für einen Knoten $x\in G$.

Sei $N_{w}=\{y\in G|y\rightarrow w\}$, die Menge der Knoten y, die direkt mit w verbunden sind (über eine Kante von y "nach" w).

Sei $gew(y,w)\!$ das Gewicht der Kante zwischen zwei direkt miteinander verbundenen Knoten y und w.

Der Abstand von v nach w ist $d(w)=min\{d(y)+gew(y,w)|y\in N_{w}\}$, das Minimum der Summe des Abstandes von v zu einem Knoten y in N plus dem direkten Abstand von diesem Knoten zu w. Oder - was kaum überrascht - wenn die Summe aller direkten Abstände von einem Knoten y in einem Pfad minimal ist, ist die die Gesamtlänge dieses Pfades (also die Summe) minimal.

Desweiteren definieren wir $M_{v}=\{y\in G|v\rightarrow y\}$ als die Menge der Knoten, die direkt mit v verbunden sind (über eine Kante von y "nach" w). (nicht signierter Beitrag von 85.181.180.135 (Diskussion | Beiträge) 16:32, 20. Jun. 2008 (CEST))

Der Algorithmus

Der Algorithmus ist eigentlich eine Verallgemeinerung der oben beschriebenen Grundlagen. Der Algorithmus teilt die Knoten von $G$ in drei Mengen ein:

$A$: die Menge der Knoten, deren kleinster Abstand zu $g_{b}$ berechnet ist

$X$: Die Menge der Knoten zu denen zwar ein Pfad ausgehend von $g_{b}$ bekannt ist, aber nicht notwendigerweise der kürzeste

$V(G)-A-X$: die übrigen Knoten von V (diese Menge wird nicht vom Algorithmus gehalten und hat daher auch keinen Namen)

Hierfür gilt selbstverständlich, dass $A\cap X=\emptyset$, A und X haben keine gemeinsamen Knoten.

Außerdem gibt es ein Array $d(v)$, indiziert mit den Knoten v von $G$. Für jeden Knoten $g\in G$ wird dieses Array vom Algorithmus so befüllt, dass am Ende gilt $d(g)=$ die Länge des kürzesten Pfads von $g_{b}$ zu $g$.

Am Anfang gilt

• $A=\{g_{b}\}$
• $X=M_{g_{b}}$
• $d(g_{b})=0$
• $\forall {g\in X}:d(g)=gew(g_{b},g)$
• $\forall {g\in V(G)-X-A}:d(g)=\infty$

Der Algorithmus wiederholt nun die folgenden Schritte bis $X$ zur leeren Menge wird (dann sind keine erreichbaren Punkte mehr übrig) ausgehend von $g_{b}$:

1. Wähle aus $X$ den Knoten $x$ mit dem minimalen Wert von d(x); das ist der Endwert von d(x) für diesen Knoten. Denn d(x) hat ja den Wert der Länge des kürzesten Pfads von $x$ ausgehend von $g_{b}$, wie wir schon bewiesen haben. Jeder andere Pfad zu $x$ muss über $x$ gehen und ist daher länger, weil alle Kanten eine positive Länge haben.
2. Damit d(x) endgültig ist, verschieben wir $x$ von $X$ nach $A$. Für alle Knoten $z$, die von $x$ aus erreicht werden können, und die noch nicht in $A$ enthalten sind, gehen wir wie folgt vor:
   1. Ist $z$ nicht in $X$ enthalten, dan fügen wir den Knoten zu $X$ hinzu. Unsere erste Abschätzung des Abstands zwischen $g_{b}$ und $z$ ist dann $d(x)+gew(x,z)$ -- diesen Wert schreiben wir in d(z).
   2. Ist $z$ schon in $X$ enthalten, dann passen wir die Abschätzung in d(z) an -- der neue Wert ist das Minimum der Länge des neu gefundenen Pfads zu $z$ ($d(x)+gew(x,z)$) und der Länge des kürzesten Pfads $z$, die wir schon gefunden haben.

Wenn sich der Algorithmus beendet (und das tut er, denn $V(G)$ ist endlich und jeder Schritt verschiebt ein Element von $X$ nach $A$), dann is d(v) befüllt mit den Abständen von $g_{b}$ zu allen Knoten die von diesem Startknoten aus erreichbar sind. Wenn d(w) unendlich ist für ein $w\in V(G)$, dann ist dieser Knoten von $g_{b}$ aus nicht erreichbar. (nicht signierter Beitrag von 85.181.180.135 (Diskussion | Beiträge) 16:32, 20. Jun. 2008 (CEST))

Vorschlag zur Zeitkomplexitaet

a) Initialisierung: Die Menge der nicht-besuchten Knoten enthält $n-1$ Elemente. Falls ein Knoten aus dieser Menge direkt mit dem Startknoten verbunden ist, wir der Abstand gespeichert, sonst als "unerreichbar" markiert. Der Knoten mit minimalem Abstand zum Startknoten wird festgehalten.

b) Der Knoten mit minimalem Gesamtabstand zum Startknoten wird aus der Menge der nicht-besuchten Knoten entfernt.

c) Die Menge der nicht-besuchten Knoten enthält im $i$-ten Schritt $n-i$ Knoten. Höchstens diese $n-i$ Knoten werden auf ihren Gesamtabstand zum Startknoten überprüft. Schritte a) und b) werden maximal $n-1$ mal widerholt. Es ergibt sich ein maximaler Auswand von $(n-1)+(n-2)+...+2+1=n(n-1)/2$

Ist zwar sehr knapp und nicht gerade formal, aber nachvollziehbar. Machts besser, wenn euch das nicht reicht. Die Abhängigkeit von der Implementierung ist richtig und wichtig. Aber was momentan geschrieben ist ist zu kompliziert und umständlich für "Normalos". Wenn ich das meinen Studenten das Laufzeitverhalten erkären will fange ich mit einfachen Überlegungen an. Nicht mit formalem Overhead. In Details geht man nachdem die Idee verstanden wurde.-- Josy2011 21:50, 28. Jan. 2011 (CET)

Der Algorithmus ist nicht greedy

Jedenfalls nicht in der Definition, wie ich sie an der Uni gelernt habe. Wesentliches Argument: es wird immer die optimale Lösung gefunden; es gibt keine lokalen Maxima bei der Lösungssuche bzw. der gefundenen Lösung. (nicht signierter Beitrag von 194.138.39.55 (Diskussion) 11:10, 21. Jul. 2010 (CEST))

Greedy-Algorithmus sagt: Sie zeichnen sich dadurch aus, dass sie schrittweise den Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis verspricht. Das tut er, siehe informeller Algorithmus, Schritt 2. --Pberndt _(DS) 11:39, 21. Jul. 2010 (CEST)

Die Wikipedia Definition sagt auch: "Ein Greedy-Algorithmus findet für ein Optimierungsproblem auf Unabhängigkeitssystemen die optimale Lösung, wenn die zulässigen Lösungen die unabhängigen Mengen eines Matroids sind. Sonst führt der Algorithmus lediglich zu einem lokalen Optimum."

Dijkstra findet jedoch immer die optimale Lösung, für beliebige Graphen. (Und warum sollten für beliebige Graphen die zulässigen Lösungen die unabhängigen Mengen eines Matroids sein?)

Abgesehen von der formalen Definition implementiert Dijkstra mit dem von Dir als "greedy" bezeichneten Mechanismus sowas wie eine Breitensuche (im Gegensatz zu Tiefensuche). Breiten-/Tiefensuche sind natürlich Begriffe, die bei Bäumen verwendet werden. Hier haben wir einen Graphen. Aber die Idee ist ähnlich: es wird vom Startpunkt eine wachsende, kugelförmige Region abgesucht.

Zu dem Zeitpunkt, an dem der nächste Knoten gewählt wird, ist global klar, dass das die (oder zuminest eine) richtige Wahl ist, die zur optimalen Lösung führt. Ein Greedy-Algorithmus wählt nach einer nicht garantiert richtigen Strategie und bleibt dann bei dieser Entscheidung, selbst wenn sie nicht optimal war. Sprich er entscheidet nach lokalem Wissen und geht "gierig" in die lokal am vielversprechendsten aussehende Richtung.

Dijkstra wertet sorgfältig alle Richtungen gleichmässig aus, und optimiert die Suchzeit mit Hilfe der sortierten Liste. Gierig wäre es (z.B.) wenn er so schnell wie möglich einen Weg zum Zielknoten suchen würde, und die Suche beendet, sobald er den ersten Weg gefunden hat.

Das ist mein Verständnis davon, was Greedy essenziell bedeutet, und wie ich sehe deckt es sich sehr gut mit der Definition in der englischen Wikipedia. Die Definition in der deutschen Wikipedia kommt mir merkwürdig vor, oder zumindest schwer verständlich. (Und wie ich sehe wird/wurde dort Dijkstra ebenfalls kontrovers diskutiert. Seit Feburar 2008 sucht man dort nach dem Matroid zu Dijkstra... offenbar erfolglos)

Die Menge E der kreisfreien Pfade ausgehend von Knoten x bildet ein Matroid mit dem Teilmengensystem U der Pfade, die in paarweise verschiedenen Knoten enden. Die Matroideigenschaften sind leicht nachzurechnen (oder nachzugooglen).

Dijkstras Algorithmus findet auch nicht "immer die optimale Lösung für beliebige Graphen", sondern nur bei nichtnegativen Kantengewichten. Der Algorithmus ist also Greedy. (nicht signierter Beitrag von 141.3.24.101 (Diskussion) 14:27, 13. Aug. 2010 (CEST))

-- 194.138.39.55 15:32, 21. Jul. 2010 (CEST)

„Zu dem Zeitpunkt, an dem der nächste Knoten gewählt wird, ist global klar, dass das die (oder zuminest eine) richtige Wahl ist, die zur optimalen Lösung führt.“ bekäme ich gerne nochmal genauer erläutert. --Zahnradzacken 21:09, 21. Jul. 2010 (CEST)

Mein Verständnis von "Greedy-Algorithmen" deckt sich ebenfalls eher mit der Ansicht das ein "Greedy-Algorithmus" schnell versucht zu einer Lösung zu kommen, dies tut indem momentan "gute" Werte (durch eine Bewrtungsfunktion, z.B. hohes Gewicht beim Rucksackproblem) ausgewählt werden und diese NICHT korregiert werden, dann wären wir ja beim backtracking.. Allerdings habe ich in der Uni bei einem sehr kompetenten Professor gelernt das der Dijkstra eine Art "Greddy-Algorithmus" sei, was mich hinsichtlich dieser Diskusion verunsichert.. Ich denke es kommt auf die Definition "Greddy" an, welche nicht einheitlich zu sein scheint und mit der, dass es um das wählen des momentan besten Folgezustand geht deckt sich das Vorgehen des Dijkstras! (nicht signierter Beitrag von 178.203.6.2 (Diskussion) 12:57, 26. Jul 2010 (CEST))

Es gibt doch keinen Grund zur Verunsicherung: Ja, Greedy-Algorithmen sind dadurch charakterisiert, dass sie in jedem Schritt eine "gute" Auswahl treffen und diese niemals korrigieren (müssen). s. auch Greedy-Algorithmus Beim Dijkstra-Algorithmus ist das Güte-Kriterium (= die "Zielfunktion" = die "Bewertung") der Abstand zum Startknoten. In jedem Hauptschritt des Algorithmus wird der bzgl. dieses Kriterium beste Knoten u ausgewählt. (Schritt 4)

Um die Beziehung zu den Matroiden besser zu verstehen, muss man sich klarmachen, dass die Lösung des Dijkstra-Algorithmus eigentlich eine Menge von KANTEN des Graphen ist. Sie enthält alle die Kanten (vorgänger[u], u), die auf einem kürzesten Weg vom Startknoten zu einem der anderen Knoten in G liegen. (Das ergibt insgesamt einen aufspannenden Baum in G.)

Also: Der Algorithmus muss unter allen Kanten des Graphen die auswählen, die für kürzeste Wege gebraucht werden. Und das macht er gierig - er nimmt immer die "billigste Kante" (billig im Sinne des Abstandes ihres Endknotens zum Startknoten!) als Fortsetzung dazu, bis alle Knoten erreicht sind (bzw. n-1 Kanten in der Lösung vorhanden).

Dass das korrekt ist und wirklich insgesamt die optimale Lösung ergibt (ohne backtracking!) muss natürlich bewiesen werden (s. Literatur [CLRS] - Dijkstra selber fand es in seinem 3-Seiten-Paper wohl offensichtlich...) Es liegt an der Matroid-Eigenschaft der Menge der zulässigen Lösungen (U = kreisfreie Teilmengen der Kantenmenge - oder s.oben) --Graf Alge 11:33, 5. Apr. 2011 (CEST)

Auch noch: Ja, selbstverständlich handelt es sich beim Dijkstra-Algorithmus auch um eine Variante der Breitensuche, welche übrigens durchaus auch allgemein für Graphen an vielen Stellen benutzt wird, genauso wie die Tiefensuche. Die Bäume sind nur ein oft vorkommender Spezialfall.--Graf Alge 11:43, 5. Apr. 2011 (CEST)

Ist das so korrekt?

"In dieser Form berechnet der Algorithmus ausgehend von einem Startknoten die kürzesten Wege zu allen anderen Knoten. Ist man dagegen nur an dem Weg zu einem ganz bestimmten Knoten interessiert, so kann man in Schritt (2) schon abbrechen, wenn der gesuchte Knoten der aktive ist."

Das ist glaube ich nicht korrekt. Wenn der Algorithmus abgebrochen wird, bevor alle Knoten besucht worden sind, besteht doch die Wahrscheinlichkeit, dass ein noch unbesuchter Knoten einen kürzeren Weg aktivieren würde. Also wenn der aktuelle kürzeste Weg aus 5 Kanten mit dem Kantengewicht 2 (=10) besteht, ist dieser Weg trotzdem länger als ein erst später "sichtbar" werdener Weg aus 2 Kanten mit einen Gewicht von je 3 (=6).

mfg -- 78.34.138.86 20:27, 1. Feb. 2011 (CET)

Das stimmt schon so. Es ist nur in dem zitierten Satz unklar, was "aktiver Knoten" heißen soll. Der aktive Knoten ist der Knoten, der im Pseudocode in Zeile 4 gewählt wird. Wenn also u:= gesuchter Zielknoten, dann kann man aufhören.

Das liegt daran, dass Dijkstra nicht den kürzesten Kanten folgt, sondern immer gerade den nächsten Knoten betrachtet, der unter allen den geringsten Wegzugewinn bedeutet. In deinem Beispiel würde, spätestens bevor die vierte Kante mit Gewicht 2 gewählt würde (das hätte eine Pfadlänge von 8 zur Folge), zunächst der Weg gewählt, der eine Summe von 6 ergeben würde.

--Zahnradzacken 22:40, 1. Feb. 2011 (CET)

"Aufgrund der Eigenschaft, einmal festgelegte Distanzen zum Startknoten nicht mehr zu verändern ..." Da stimmt doch etwas nicht?! Wenn man das im Artikel gezeigte Beispiel (die Animation) ansieht, dann erkennt man, dass sich sehr wohl die Kosteneinträge einzelner Knoten im Laufe der Abarbeitung ändern können. 95.116.130.69 18:47, 14. Nov. 2011 (CET)

Die Distanz wird erst „festgelegt“, wenn man dann tatsächlich diesen Knoten besucht. Die Formulierung ist aber i.d.T. unglücklich. --Chricho ¹ 16:49, 15. Nov. 2011 (CET)

Negative Kantengewichte

Der Dijkstra-Algorithmus gilt auch für negative Kantengewichte, wenn man zu allen Kantengewichten 1-Minimum(Alle Kantengewichte) dazuzählt. Vom entgültigen Weg ist dann der Summand mal besuchter Knotenzahl wieder abzuziehen. (nicht signierter Beitrag von Bemdev (Diskussion | Beiträge) 17:52, 9. Apr. 2011 (CEST))

Das geht zwar praktisch aber es wiederspricht dem Sinn des Algorithmus. Der Aglorithmus bestimmt die kürzeste Verbindung zwischen zwei Knoten in einem Graphen. Und es kann keinen Weg geben der kleiner als Null ist. Sonst wäre man ja da bevor man losgelaufen ist. -- Hoben19 15:48, 28. Apr. 2011 (CEST)

Man wäre nicht da, bevor man losgelaufen ist. Die Kantengewichte beschreiben nicht zwangsweise die Weglänge. Es sind nur Zahlen, deren Summe man minimieren möchte. Das können dann in der Realität Kilometer, aber auch Fahrtzeiten, Kosten (negative Kosten könnten dann Gewinn bedeuten), Steigungen, zusteigende Personen oder etwas ganz anderes sein.

Praktisch funktioniert das aber natürlich auch dann nur, wenn es keine negativen Zyklen gibt. Der Algorithmus müsste also zusätzlich den Graphen noch auf Zyklen prüfen und außerdem von Beginn an alle Kantengewichte kennen. Eine lokale Erkundung der Gegend (etwa beim Routing) wäre dann nicht möglich. --Zahnradzacken 15:12, 29. Apr. 2011 (CEST)

Dafür gibt es den Bellman-Ford-Algorithmus - der findet die Kreise negativer Länge. Der Floyd-Algorithmus kann immerhin mit negativen Gewichten umgehen. Dijkstra dagegen nicht! Der Vorschlag von Bemdev oben ist falsch, da die Wege ja aus unterschiedlich vielen Kanten bestehen können. Schaut einen Beispielgraphen mit 4 Kanten an: $w(a,b)=2,w(a,c)=5,w(c,b)=-4,w(b,d)=2$ Der kürzeste Weg von a nach d ist offenbar a-c-b-d mit der Länge 3. Addiert man nun zu allen Kantengewichten 5, bekommt dieser Weg die Länge 18. Dijkstra findet ihn aber nicht, da der Weg a-b-d nur die Länge 14 hat.--Graf Alge 00:23, 2. Mai 2011 (CEST)

Vielen Dank für dieses Beispiel und die Klarstellung. Es wäre aber nett, wenn du deine Änderungen am Artikel etwas begründen könntest: warum wird aus "nicht-zusammenhängend" "nicht zusammenhängend"? Und warum hast du die Wikilinks auf den Glossar Graphentheorie entfernt? --Zahnradzacken 18:34, 2. Mai 2011 (CEST)

Äh, findest Du es so nicht besser? - Also gut, für Dich meine Gründe: "zusammenhängend" ist die wohldefinierte Eigenschaft von Graphen, um deren Fehlen es hier geht. Der Link war irreführend - jede Kante hat einen Startknoten (im Glossar beschrieben) - bei Dijkstra geht es aber darum, dass ein Knoten des Graphen als Startknoten ausgezeichnet wird. Beides hat nicht viel miteinander zu tun. Ich denke, Links sollten nicht so viele wie irgend möglich gesetzt werden, sondern immer zu Stellen führen, wo man zusätzliche Informationen findet, die einen Bezug zum Thema haben - vor allem benutzte Begriffe näher erklären.--Graf Alge 01:28, 3. Mai 2011 (CEST)

Was den Link zum Glossar angeht, hatte ich mir nicht die Mühe gemacht, zu schauen, ob es passt. Dein Argument ist natürlich überzeugend. Vielleicht hätte eine Bemerkung dazu noch im Zusammenfassungs-Feld Platz gehabt :) Man könnte aber auch überlegen, den Glossar zu verbessern, immerhin wird auch dort das Wort Startknoten auch für Wege verwendet. --Zahnradzacken 11:34, 3. Mai 2011 (CEST)

Dem stimme ich zu. Ehrlich gesagt, liegt für mich das Graphen-Glossar schon lange auf meiner (virtuellen) Liste namens "Mal vornehmen, wenn ich richtig viel Zeit habe und solange zumindest im Auge behalten" Aber Du weißt vermutlich auch, wie das mit der unausgefüllten Zeit so ist... --Graf Alge 11:18, 4. Mai 2011 (CEST)

Da "zusammenhängend" wohldefiniert ist, ist das Gegenteil auch wohldefiniert, man könnte also auch von der Eigenschaft "nichtzusammenhängend" sprechen, ganz wie "nichtnegativ". Die Details der deutschen RS kenne ich hier nicht genügend, aber in vielen Fällen ist der Lesbarkeit wegen ein Bindestrich bei zusammengesetzten Wörtern zulässig. Ich finde diese vielen Leerzeichen in einer Nominalphrase anstrengend. Aber Zusammenhang von Graphen liefert schon die Lösung: Die umgekehrte Eigenschaft heißt in Wirklichkeit unzusammenhängend. --Zahnradzacken 11:34, 3. Mai 2011 (CEST)

Stimmt, hab ich wohl auch schon in manchen Lehrbüchern oder Skripten so gelesen. Dann können wir das kürzere Wort ja auch benutzen. Ich änder es gleich noch mal.--Graf Alge 11:18, 4. Mai 2011 (CEST)

Berechnet der Algorithmus einen oder alle Wege?

Meiner Meinung nach berechnet der Algorithmus bei normalem (nicht abgebrochenem) Durchlauf ALLE kürzesten Wege vom Startknoten zu ALLEN anderen Knoten. Wer auf der Seite des Algorithmus mal das Beispiel durchläuft wird auch sehen, dass nach der Terminierung des Algorithmus nicht nur der kürzeste Weg von Frankfurt nach München berechnet wurden, sondern Alle kürzesten Wege von Frankfurt zu jedem anderen Knoten. -- Hyperjonny 21:24, 12. Dez. 2011 (CET)

Steht doch im Artikel? --Zahnradzacken 00:09, 13. Dez. 2011 (CET)

Entfernungen und Verbindungen im Straßen-Beispiel

Das Straßenbeispiel am Ende des Artikels muss ein Norddeutscher gemacht haben, oder es wurde ein Beispiel aus einem anderen Land importiert und die Städtenamen eingedeutscht.

Von Frankfurt nach Würzburg sind es keine 217 km, sondern nur 119, also gut halb so weit. Von Würzburg kommt man über die A81 direkt und viel schneller nach Stuttgart als über Nürnberg...

Gpermant (Diskussion) 18:28, 18. Apr. 2012 (CEST)

Besseres Beispiel (?)

Das Beispiel das aufzeigt, dass negative Kanten das Ergebnis verfälschen können ist ein schönes und plakatives Beispiel, das ist wahr! Aber es ist insofern ein falsches Beispiel als das der Dijkstra-Algorithmus in diesem Beispiel niemals den längeren Weg auswählen würde und somit auf das verfälschende -3 stoßen würde, da die Exploration des unteren Weges bereits beim ersten Kantengewicht von 4 aufhört und nicht wieder aufgenommen wird bevor das Ziel erreicht ist. Oder ist es tatsächlich so, dass in jedem Fall der untere Weg auch untersucht wird, obwohl oben schon ein Zielweg erreicht wurde, der insgesamt "kürzer" ist als der Weg zum ersten Knoten im unteren Weg? -- Ilker Savas (Diskussion) 11:29, 20. Mai 2012 (CEST)

Einerseits ist es richtig, dass die Kante mit Gewicht -3 nie erreicht würde. Andererseits wundert es mich, dass du die Kante als "verfälschend" bezeichnest. Wenn man negative Kantengewichte will, dann verfälschen sie nichts. Der Fehler vom Dijkstra-Algorithmus ist, dass er den kürzeren Weg über -3 nicht findet (Summe 1) und den längeren Weg (Summe 2) für den Kürzeren hält. --Zahnradzacken (Diskussion) 18:10, 20. Mai 2012 (CEST)

Ach soo rum ist das.. jetzt habe ich verstanden was da genau gemeint ist :), thx! -- Ilker Savas (Diskussion) 18:51, 20. Mai 2012 (CEST)

Minimalbeispiel für fehlerhaftes Ergebnis des Dijkstra-Algorithmus

Es wird im Artikel kurz erwähnt, dass der Dijkstra-Algorithmus nur funktioniert, wenn alle Kanten nicht-negative gewichte haben. Hier ist ein kleines Beispiel für einen Graphen, auf dem Dijkstra ein falsches Ergebnis liefert:

Will das jemand einbinden? edit: Ich habe gerade gesehen, dass es so was schon gibt. --Martin Thoma 16:28, 14. Jul. 2012 (CEST)

Der Artikel enthält einen ganzen Absatz darüber, inklusive das Bild . --Zahnradzacken (Diskussion) 17:24, 14. Jul. 2012 (CEST)

Dieser Abschnitt kann archiviert werden. Martin Thoma 10:19, 30. Jul. 2012 (CEST)

Pseudocode: Methode vs. Funktion

Warum steht im Pseudocode mal Methode, mal Funktion? Martin Thoma 10:19, 30. Jul. 2012 (CEST)

Das ist wohl die Pascal-Brille, wonach Methoden im Gegensatz zu Funktionen keinen Rückgabewert haben. Eine Unterscheidung, die bei Pseudocode vielleicht nicht besonders zum Verständnis beiträgt. Kannst du gerne verbessern. Zahnradzacken (Diskussion) 12:18, 30. Jul. 2012 (CEST)

Defekter Weblink

• http://algo2.iti.uni-karlsruhe.de/adw.php (Internet Archive)

– GiftBot (Diskussion) 10:29, 1. Sep. 2012 (CEST)

erledigtErledigt--- *Bene* (Meine Diskussion) --- 09:50, 2. Sep. 2012 (CEST)

(sry)

Dieser Abschnitt kann archiviert werden. --- *Bene* (Meine Diskussion) --- 09:53, 2. Sep. 2012 (CEST)

Inkonsistenz in "Informelle Darstellung"

Im o.g. Abschnitt steht Eine einmal berechnete Distanz zwischen dem Startknoten und einem erreichten Knoten wird nicht mehr geändert.

Die Abbildung daneben (die mit drei Bildern á drei Knoten) zeigt aber das Gegenteil.

Ich bitte um Aufklärung (da ich selber nicht weiß wie es richtig ist). 92.74.109.204 17:41, 8. Jul. 2013 (CEST)

Die informelle Beschreibung und die Grafik quetschen viel Information auf engen Raum. Folgendermaßen passen Bild und Grafik zusammen: Es werden Distanzen zu Knoten berechnet, die sich noch verringern können. Sobald aber ein Knoten als "erreicht" betrachtet wird, weil er unter allen Knoten, die einen Zwischenwert haben, den geringsten Zwischenwert hat, wird dieser Zwischenwert als "Distanz vom Startknoten zum erreichten Knoten" genommen und ab jetzt nicht mehr geändert. --Zahnradzacken (Diskussion) 00:17, 9. Jul. 2013 (CEST)

Entfernung Frankfurt - Würzburg

Im Beispiel beträgt die Entfernung von Frankfurt/M nach Würzburg 217 km. In der Realität sind es aber ca. 117 km. (nicht signierter Beitrag von 178.0.96.26 (Diskussion) 21:11, 22. Jun. 2014 (CEST))

"Die Werte eines willkürlich gewählten Beispiels entsprechen nicht der Realität." mimimimimimi! (nicht signierter Beitrag von 89.204.135.47 (Diskussion) 08:33, 13. Aug. 2015 (CEST))

Dijkstra ist sicher kein Greedy-Algorithmus!

Ich habe den falschen Hinweis "Dijkstra ist greedy" gelöscht; wenn, dann gehört Dijkstra zu den DP-Algorithmen, siehe auch englische Seite zum Algorithmus. Die Quelle ist, mit Verlaub, absurd.

Doch, das ist genau der klassische Fall eines Greedy-Algorithmus: die getroffenen Entscheidungen werden nicht wieder zurückgenommen (salopp: kein rumprobieren)... so hatte ich das jedenfalls mal gelernt.

Ich stelle gerade fest, daß "Greedy-Algorithmus" hier etwas anders definiert wird... huh, muß wohl erstmal was recherchieren.

Ach, nächstes mal bitte Unterschreiben (zwei Minusse und vier Tilden). --H.Marxen (Diskussion) 20:46, 13. Jun. 2017 (CEST)

Zur Info: im englischen Artikel steht dazu: „The process that underlies Dijkstra's algorithm is similar to the greedy process used in Prim's algorithm.“ Klar wie Kloßbrühe. Grr. --H.Marxen (Diskussion) 20:54, 13. Jun. 2017 (CEST)

In

Algorithmen und Datenstrukturen: Die Grundwerkzeuge

Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders

Heidelberg, 2014

Seite 307

findet man

„Die Bezeichnung Greedy-Algorithmus [...] wird für eine algorithmische Strategie benutzt, bei der die betrachteten Objekte in einer gewissen (meist sorgfältig gewählten) Reihenfolge nacheinander betrachtet werden, und eine Entscheidung über ein Objekt (z. B. ob es in die Lösung aufgenommen wird oder nicht) in dem Moment getroffen wird, in dem dieses Objekt betrachtet. Einmal getroffene Entscheidungen werden nachher nie mehr geändert.“

Allerdings finde ich nichts darüber, ob Dijkstra ein Greedy Algorithmus ist.

Aus

E. Horowitz, S. Sahni, S. Rajasekaran

Computer Algorithms

New York, 1998

Chapter 4, The Greedy Method

4.8 Single-Source Shortest Paths

Seite 244

„This Algorithm (known as Dijkstra's Algorithm) [...]“

ergibt sich aus den Kapitelüberschriften, dass Dijkstras Algorithmus als Greedy-Algorithmus aufgefasst wird.

In

A. Aho, J. E. Hopcroft, J. D. Ullman

Data Structures and Algorithms

CHAPTER 6: Directed Graphs

6.3 The Single Source Shortest Paths

findet man folgenden Hinweis:

„To solve this problem we shall use a "greedy" technique, often known as Dijkstra's algorithm.“

Ebenso in

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein

Introduction to Algorithms

Third Edition

Cambridge, Massachusetts London, England, 2009

VI Graph Algorithms

24 Single-Source Shortest Paths

24.3 Dijkstra’s algorithm

Seite 659

„Because Dijkstra’s algorithm always chooses the “lightest” or “closest” vertex in $V-S$ to add to set $S$, we say that it uses a greedy strategy. [...] Greedy strategies do not always yield optimal results in general, but as the following theorem and its corollary show, Dijkstra’s algorithm does indeed compute shortest paths. [...]“

Bei Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne habe ich keine Bemerkung gefunden, daß Dijkstras Algorithmus ein Greedy-Algorithmus ist.

--Miracle173 (Diskussion) 21:12, 7. Jul. 2018 (CEST)

Animation

Animation ist hübsch, aber unsinnig. So schnell kann man gar nicht schauen und rechnen, wie die Animation an einem vorbeirauscht. Didaktisch völlig daneben.2003:F7:AF14:7E00:4D90:4A1D:3B1E:8B80 00:35, 23. Sep. 2020 (CEST) D. May

Zum "in Ruhe verstehen" gibt es unten speziell das lange Beispiel. 10 große Bilder kann man aber nicht an den Anfang setzten. Die Animation ist eine visuelle Orientierung für Leute die mit "Dijkstra" nichts assoziieren: es geht um "Knoten", "Kanten", ein "Algo tackert" da durch. Ein paralleles Mitrechnen ist nicht das Ziel; man kann auch keine Geschwindigkeit finden die allen gerecht wird. Andererseits wäre es auch kein Problem die Frames etwas langsamer zu machen, wenn das Mehrheitsmeinung ist. --Jahobr (Diskussion) 11:45, 23. Sep. 2020 (CEST)