shortest-path

Fragen
Kürzeste Pfadprobleme sind Probleme beim Suchen des kürzesten Pfads von einer einzelnen Quelle zu einer Zielquelle, normalerweise in einem Diagramm.
3
Antworten

Kürzester Pfad in Abwesenheit der gegebenen Kante

Angenommen, wir erhalten einen gewichteten Graphen G (V, E). Das Diagramm enthält N Scheitelpunkte ( Von 0 bis N-1 nummeriert ) und M bidirektionale Kanten . Jede Kante (vi, vj) hat positiven Abstand d (dh der Abstand zwischen den b...
05.06.2012, 10:01
2
Antworten

Lösen einer Erweiterung des kürzesten Hamilton-Pfads

Ich habe über eine Erweiterung des Shortest Hamiltonian Path (SHP) -Problems nachgedacht und konnte keine Lösung finden. Ich weiß, dass es NP-komplett ist, aber ich dachte, ich würde hier nach Ideen fragen, da ich das Problem nicht einfach nur b...
06.11.2012, 08:29
2
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
1
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
3
Antworten

Wie finde ich den kürzesten Pfad in einem gerichteten Graphen, der Kantengewichte von 0 oder 1 in linearer Zeit hat?

Ich suche nach einer Möglichkeit, die BFS-Methode zu verbessern, mit der die kürzesten Pfade aus einer Quelle in einem ungewichteten gerichteten Graphen gefunden werden können, und das obige Problem in O (N + M) -Zeit zu lösen. N ist die Anzahl...
02.02.2014, 16:55
4
Antworten

Ermitteln aller kürzesten Pfade von jedem Knotenpaar in einem Diagramm

Ich habe etwa 70.000 Knoten und 250.000 Kanten, und der Graph ist nicht notwendigerweise verbunden. Offensichtlich ist die Verwendung eines effizienten Algorithmus entscheidend. Was empfehlen Sie? Als Nebenbemerkung würde ich mich darüber fre...
10.03.2010, 23:57
1
Antwort

Druck des kürzesten Weges s / w gegebenen Knoten mit modifiziertem floyd warshall

Ich lese den Ansatz von Wikipedia , um den kurzen Pfad s / w zwei gegeben zu drucken Punkte in einer Grafik durch Ändern des Floyd Warshall-Algorithmus. Ich habe dies codiert, aber es gibt nicht die erwartete Ausgabe: Initialisiert alle El...
06.11.2013, 13:45
1
Antwort

Den kürzesten Pfad mit FGL finden

Ich verwende Martin Erwigs Functional Graph Library (FGL), um den folgenden einfachen gewichteten gerichteten Graph darzustellen. %Vor% Ich möchte jetzt den kürzesten Weg von einem Knoten zum nächsten finden, z. A bis E mit dem Al...
28.10.2012, 23:30
2
Antworten

Algorithmus zum Entfernen der wenigsten Kanten, um die Längenzunahme des kürzesten Pfades in einem ungewichteten ungerichteten Graphen zu erzwingen

Gibt es eine Adjazenzmatrix für einen ungewichteten ungerichteten Graphen, gibt es einen effizienten Weg (Polynomialalgorithmus), um die Länge des kürzesten Weges zwischen irgendwelchen gegebenen zwei Knoten s und t zu erweitern / zu erhöhen?...
24.01.2013, 07:44
1
Antwort

Eppsteins Algorithmus und Yens Algorithmus für k kürzeste Wege

Ich versuche genau zu verstehen, wie diese Algorithmen funktionieren, aber ich konnte keine einfache Erklärung finden. Ich würde es sehr schätzen, wenn mir jemand eine Beschreibung dieser Algorithmen liefern oder auf sie hinweisen könnte, die le...
13.10.2012, 05:03