Diskussion:Dijkstra-Algorithmus

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis 1 Einleitung 2 Dijkstra != MST (Kruskal) 3 Algorithmus 4 Grundlegende Konzepte und Verwandschaften 5 Verallgemeinerung Falsch 6 Allgemeines 7 Initialisierung 8 Zweiseitige Dijkstra-Algorithmus 9 Nicht ganz klar 10 Noch eine Frage zur Initialisierung 11 Änderungen am eigentlichen Algorithmus 12 Fehler in den Grafiken 13 Dijkstra <-> A* 14 Zeitkomplexität 15 Vorschlag zum Löschen 16 Beispiel 17 Frage zu negativen Kantengewichten

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] 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?

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] Ä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)

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] 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)

[Bearbeiten] 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.

Contra 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.

Contra 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)

[Bearbeiten] 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)

[Bearbeiten] Frage zu negativen Kantengewichten

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)