Ich habe eine bi-gerichteten gewichteten Graphen mit etwa 5000 Knoten und ich habe eine Liste von "wichtigen" Knoten (100 oder so). Wie finde ich bei einem Startknoten und einem Endknoten den kürzesten Abstand zwischen diesen beiden Knoten, die mindestens einen der "wichtigen" Knoten passieren. Beachten Sie, dass keine negativen Kanten vorhanden sind. Ich implementierte den Dijkstra-Algorithmus, um die kürzeste Entfernung bei zwei Knoten zu finden. Und die einzige Art, wie ich dieses Problem lösen könnte, wäre, die Liste der wichtigen Knoten durchzugehen, die Entfernung von Start -> Wichtiger Knoten # 1 -> Ende für alle wichtigen Knoten zu finden und dann das Minimum zu nehmen. Gibt es einen schnelleren Weg, dies zu lösen?Wie findet man den kürzesten Abstand zwischen zwei Knoten, die mindestens einen der obligatorischen Knoten passieren?
0
A
Antwort
1
Ihr Ansatz ist absolut richtig, was Sie brauchen, ist Dijkstra weniger oft anzuwenden. Dieses Problem kann leicht gelöst werden, indem Dijkstra nur zweimal angewendet wird.
Bewerben Dijkstra mit Start als Quelle. Speichern Sie die Abstände in Array fromS.
Wenden Sie Dijkstra noch einmal an. Dieses Mal nehmen Sie Ende als Quelle. Speichern Sie die Abstände im Array bis E. Da Ihre Grafik ungerichtet ist die kürzeste Entfernung von Ende Knoten zu jedem anderen Knoten ist der kürzeste Abstand von jedem anderen Knoten zu Ende Knoten. (Das ist der Trick).
Suchen Sie die erforderliche kürzeste Entfernung.
For node in importantNodes : ans = min (fromS [node] + toE[node] , ans) return ans
Verwandte Themen
- 1. Directed gewichteten Graph kürzesten Weg mit obligatorischen Knoten zu passieren
- 2. Abstand zwischen den Knoten in floyd warshall
- 3. Java Binary Trees: Den Knoten finden, der zwei Knoten mit der kürzesten Entfernung erreicht
- 4. Wie Optionen passieren Knoten, wenn babel-Knoten
- 5. Wie Knoten vollständig zwischen zwei bestimmten Knoten
- 6. jgraphx: Hierarchisches Layout verkleinere den Abstand zwischen den Knoten
- 7. Wie man Programm beschleunigt, das den kürzesten Weg zwischen zwei wikipedia Artikeln findet
- 8. Der beste Weg, um einen kürzesten Weg zwischen zwei Knoten in Tinkerpop zu finden 3.1
- 9. Wie findet man den längsten Pfad in einem zyklischen Graph zwischen zwei Knoten?
- 10. Berechnen Sie den Abstand zwischen den Knoten in AdjacencyMatrix
- 11. Wie berechnet man den Abstand zwischen zwei Knoten in GraphX, Scala?
- 12. Wie findet man Knoten vor einem bestimmten Knoten mit Roslyn?
- 13. Gibt es einen bekannten Algorithmus zum Finden der kürzesten Entfernung zwischen Knoten mit demselben Abstand zwischen jedem Paar?
- 14. Wie man Abstand zwischen Knoten in graphviz verwaltet?
- 15. Abstand zwischen zwei Knoten in einem Baumalgorithmus Problem
- 16. XSLT: Zählen Knoten zwischen zwei bestimmten Knoten
- 17. Extract Knoten zwischen zwei Knoten aus XML
- 18. Wie man einen bestimmten Knoten in Neo4j findet
- 19. Wie findet man Knoten-ID in NS2?
- 20. Finden Sie die versteckten Knoten zwischen zwei Knoten - Grafik - Java
- 21. Wie findet man gemeinsame Nachbarn unter Knoten?
- 22. Wie erhält man eine Polylinie für den kürzesten Weg zwischen zwei Punkten in der Broschüre?
- 23. Berechnen Sie den kürzesten Weg mit genau `n` Knoten zwischen zwei Punkten auf einer meshgrid
- 24. Längster Pfad zwischen zwei Knoten
- 25. Networkx: Ermitteln Sie die Entfernung zwischen Knoten
- 26. Finde den kürzesten Abstand zwischen A und B in Node.JS
- 27. müssen kürzesten Weg zwischen zwei Knoten, basierend auf einem der Knoten des Eigenschaftswert -verwenden JAVA und 3.0.1 Neo4j Version
- 28. Get alle Routen zwischen zwei Knoten neo4j
- 29. welcher Algorithmus kürzesten Weg von einem Knoten auf einem anderen Knoten vom Typ X
- 30. den Abstand auf Knoten eines Dendrogramme