Diskussion:Dijkstra-Algorithmus

Automatische Archivierung

Auf dieser Seite werden Abschnitte montags automatisch archiviert, deren jüngster Beitrag mehr als 365 Tage zurückliegt und die mindestens 2 signierte Beiträge enthalten. Um die Diskussionsseite nicht komplett zu leeren, verbleiben mindestens 3 Abschnitte. Das aktuelle Archiv befindet sich unter Archiv.

Quelle für das Routenplaner Beispiel?

Routenplaner werden immer gerne als Beispiel für den Dijkstra und A*-Algorithmus genutzt, obwohl die Hersteller von Navigationssystemen meistens vorgefertigte Listen benutzen, um die Routenberechnung zu beschleunigen. Übrigens eignet sich Dijkstra auch sehr gut für eine Umgebungssuche ohne konkretes Ziel (z.B. eine beliebige Tankstelle in der nähe) (nicht signierter Beitrag von 91.53.144.64 (Diskussion) 6. Mai 2012, 02:05 Uhr)

nö (nicht signierter Beitrag von 84.146.93.54 (Diskussion) 20. Januar 2015, 09:24 Uhr)

Negative Kantengewichte

Ich habe gerade eben einen Satz aus dem Artikel entfernt, der meiner Meinung nach falsch war. Zitat:

„Die Kantengewichte des Graphen dürfen dabei grundsätzlich auch negativ sein, jedoch terminiert der Algorithmus nicht bei der Existenz von Kreisen negativer Länge, die vom Startknoten aus erreichbar sind.“

Zunächst einmal findet der Dijkstra-Algorithmus nur bei nicht-negativen Kantengewichten den kürzesten Weg. Ein Gegenbeispiel ist sogar im Abschnitt "Informelle Darstellung" gegeben.

Zweitens passt die Aussage, der Algorithmus würde bei der Existenz von Kreisen negativer Länge nicht terminieren, meiner Meinung nach nicht zu dem Pseudocode, der im Artikel gegeben ist. Der dort gegebene Algorithmus hat zwei Schleifen: Die äußere Schleife wird so oft aufgerufen, bis die Priority Queue Q leer ist, wobei in jeder Iteration ein Element aus Q entfernt wird. Die innere Schleife ("für jeden Nachbarn v von u") wird ebenfalls nur endlich oft aufgerufen. Daher müsste der Algorithmus doch auch im Fall negativer Kreise immer terminieren. Bitte korrigiert mich, wenn ich falsch liege. --Thomaswm (Diskussion) 16:32, 1. Feb. 2015 (CET)

Uniform cost search

Da der englische Wikipedia Artikel zu Uniform Cost Search auf diesen Artikel verweist, wäre es eventuell ganz klug auch was dazu in diesem Artikel zu erwähnen. (nicht signierter Beitrag von 37.24.103.210 (Diskussion) 16:24, 21. Feb. 2016 (CET))

Unvollständiger Zeitkomplexität-Abschnitt?

Hallo,
im Abschnitt zur Zeitkomplexität wurde ein Großteil auskommentiert und der Abschnitt unvollständig gelassen. Ich habe jetzt nichts dazu im Diskussionsarchiv gefunden, soll der auskommentierte Text also wieder mit reingenommen oder neu geschrieben werden? BSMFaktor (Diskussion) 18:45, 30. Aug. 2016 (CEST)

Manheim

Warum steht bei den Beispielgrafiken immer Manheim, statt Mannheim? Zumindest bei den ersten beiden ist es richtig geschrieben.

Beschreibung des Algorithmus

Ein gutes Beispiel warum man sich gar nicht erst mit deutschsprachigen Artikeln zu komplexen Themen beschäftigen sollte. Da wird ein Algorithmus hin geklatscht, bei dem man sich das meiste selbst zusammen denken muss, weil Grundlegendes nicht genannt wird. (nicht signierter Beitrag von 84.157.115.239 (Diskussion) 10:09, 18. Jun. 2020 (CEST))

Hintergrund, Geschichte, Bedeutung, Rezeption

Was mir komplett fehlt, weswegen ich diesen Artikel eigentlich überhaupt aufgerufen habe, ist das "Drumherum" - wann/wie ist er entstanden, wann/wo wurde er veröffentlicht, was gab es vorher an Kürzeste-Wege-Algorithmen (m.W. was Moore bis dato der Goldstandard), warum ist er so bedeutend, wie wird er in der nachfolgenden Zeit und (Fach-) Literatur wahrgenommen, welchen Einfluss hat er auf die Informatik, warum gilt er bis heute als einer der elegantesten Algorithmen... Ein paar Hinweise zu solchen Fragen sind in dem verlinkten VICE-Artikel (dessen Link ich heute korrigiert habe), und in dem dort wiederum verlinkten Interview. Zum Algorithmus selber wäre interessant: Was ist eigentlich die Grundidee (nämlich dass in jedem Schritt zu einem weiteren Knoten der kürzeste Pfad gefunden wird, und m.M.n. die Tatsache, dass hierbei eben die Kantenund nicht die Knoten betrachtet werden - aber da bin ich nicht sicher, und auch dazu gibt es bestimmt gute Quellen, bzw. das lässt sich elegant in 2 Sätzen formulieren. Ein Abschnitt zu solchen Themen täte dem Artikel gut, ich kann leider nicht viel dazu beisteuern (ich bin ja eben gerade auf der Suche nach solchen Infos). Was haltet ihr davon? (nicht signierter Beitrag von 2.201.6.33 (Diskussion) 12:01, 3. Okt. 2020 (CEST))