dijkstra, Seitenzahl 1

Der von dem niederländischen Informatiker Edsger Dijkstra entwickelte Dijkstra-Algorithmus ist ein Graphsuchalgorithmus, der das Problem des Single-Source-Shortest-Paths für einen verbundenen Graphen mit nichtnegativen Edge-Pfad-Kosten löst und einen Baum für den kürzesten Pfad erzeugt. Dieser Algorithmus wird häufig beim Routing und als Subroutine in anderen Graphalgorithmen verwendet.

Antworten

Kann Dijkstras Single Source Shortest Path Algorithmus einen unendlichen Zyklus in einem Graphen erkennen?

So kam ich zu diesem schönen Problem, das Sie auffordert, ein Programm zu schreiben, das feststellt, ob in einem gerichteten Graph ein negativer unendlicher kürzester Pfad existiert. (Man kann sich auch vorstellen, ob ein "negativer Zyklus" im G...

21.11.2013, 14:05

Antworten

Gibt es schnellere Algorithmen als Dijkstra?

Gibt es einen gerichteten, verbundenen Graphen mit nur positiven Kantengewichten, gibt es schnellere Algorithmen, um den kürzesten Weg zwischen zwei Scheitelpunkten zu finden, als Dijkstra mit einem Fibonacci-Haufen? Wikipedia sagt, dass Dijk...

09.11.2009, 14:16

Antworten

Vorschläge für die einfachsten Algorithmen für einige Graph-Operationen

Die Frist für dieses Projekt ist sehr schnell abgelaufen und ich habe nicht viel Zeit, um mich mit dem zu beschäftigen, was noch übrig ist. Anstatt nach den besten (und wahrscheinlich komplizierteren / zeitaufwendigeren) Algorithmen zu suchen, s...

15.04.2010, 16:44

Antwort

AStar - Erklärung des Namens

Ich suche nach einer Erklärung, warum der AStar / A * -Algorithmus AStar heißt. Alle ähnlichen Algorithmen (Kürzestpfadproblem) werden oft wie ihre Entwickler benannt. Wofür steht AStar also?

06.04.2015, 11:21

Antworten

Warum Dijkstras Algorithmus Heap (Priority Queue) verwendet?

Ich habe versucht, den Algorithmus von Dikstra auf zyklisch gewichteten Graphen zu verwenden, ohne die Prioritätswarteschlange (Heap) zu verwenden, und es hat funktioniert. Dann habe ich google gesucht, "warum zur Hölle brauchen wir eine Prio...

18.09.2012, 16:34

Antworten

Kürzester Pfad unter Verwendung des Dijkstra-Algorithmus

Ich reaktiviere gerade eine alte Hausaufgabe, in der ich ein Programm schreibe, das unter anderem die Suche nach dem kürzesten Pfad in einem Graphen mit Dijkstras Algorithmus beinhaltet. Ich denke, ich habe es größtenteils richtig gemacht, ab...

05.07.2011, 15:33

Antwort

JUnit Testfall über private Methode im Dijkstra-Algorithmus

Ich versuche herauszufinden, wie man am besten einen Testfall für eine Klassenübung implementiert. Meine Klassenübung liefert den bekannten Fehler und damit sollte ich einen Testfall schreiben, damit dieser fehlschlägt und somit den Fehler finde...

30.04.2015, 11:48

Antworten

Können wir Dijkstras Algorithmus ändern, um mit negativen Gewichten zu arbeiten?

Der Pseudocode aus Wikipedia: %Vor% Nun sehen wir in Zeile 14, dass die Relaxation nur auf Nachbarn von u angewendet wird, die noch nicht von Q entfernt wurden. Aber wenn wir auch Nachbarn von u nehmen, die aus Q entfernt wurden,...

29.05.2012, 13:15