Diskussion:Dijkstra-Algorithmus

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)

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üft. --21:36, 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.

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

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)