k-kürzeste (alternative) Pfadalgorithmus, Java-Implementierungen

Question

Können Sie eine Java-Bibliothek empfehlen, die k-kürzesten Algorithmus implementiert -> Suche nach alternativen Möglichkeiten, nicht die einzige kürzeste in gerichteten Multigraph?

Ich habe nur JGraphT gefunden, aber es gibt tatsächlich Bug (den ich eingereicht habe), aber es wird eine Menge Zeit brauchen, um es zu reparieren, denke ich, gibt es noch andere verfügbare Implementierungen? Außer JGraphT fand ich nur kleine Ein-Mann-Projekte:/

ODER wäre schwer zu ändern Disjktra kürzesten Pfad alg alternative Pfade anzuzeigen?

Dank

Answer 1

2 Mögliche Optionen:

Option 1. Die class KshortestPath von the MascOpt Package ist eine gute Wahl für ein Java-Implementierung von k-kürzesten Wegen.

Option 2. Sie auch diese aus code.google.com versuchen Dies scheint ein eine Person, die Anstrengung zu sein, aber die gute Nachricht ist, dass der Algorithmus geteilt wird. Yens Ranking - die Details sind hier (http://www.ohloh.net/p/k-shortest-paths)

Hinweis: Das Finden der kürzesten Pfade zwischen allen Knotenpaaren in einem gegebenen Diagramm ist ein anderes Problem. Sehen Sie diese SO Frage auf Dijkstra vs. Floyd-Warshall.

Beachten Sie auch, dass k-shortest paths für Rich-Graphen tendenziell leichte Variationen des (Dijkstra) kürzesten Pfads sind - alternative Pfade zwischen Knoten auf dem kürzesten Pfad mit etwas höheren Kosten.

Ich weiß, dass das OP nach Java-Implementierungen gefragt hat, aber wenn die Leute die Wahl haben und R eine Option ist, ist auch die kBestShortestPathspackage von CRAN eine sehr gute Option.

Hoffe, dass hilft.

Answer 2

Es bevor eine ähnliche Anfrage wird, aber für alle Pfade auf Stackoverflow suchen. Find all paths in a graph with DFS

hoffte, das hilft, sie aber nicht mit der genauen Lösung beantwortet wurde, sondern eher eine Führungs

Answer 3

Das Finden der k-kürzesten Pfade ist verwandt, aber nicht das gleiche Problem wie alternative Pfade. Gute alternative Wege sind komplizierter. Have a read wo andere ähnliche Ansätze skizziert werden:

• k-Kürzeste Wege
• Pareto Optimalitäts
• Plateau Methode
• Penalty Ansatz

Das Plateau-Methode ist ein bisschen here dargestellt.

Wenn es Ihnen möglich Deutsch zu lesen dann this lecture is nice:

• z.B.Optimierung in Bezug auf Zeit oder Distanz => Problem: interessante Alternativen fehlen
• dijunct Pfade => gleiches Problem
• k-kürzeste Wege => Problem: die echte Alternative ist wahrscheinlich nicht unter den ersten 1000 Pfaden

Page 5

So sagt uns die Intuition: Eine Alternative sollte nahezu identische Entfernung oder Zeit haben. aber sollte deutlich anders sein. so die erste Idee: Finde einen Pfad, der Länge UND Ähnlichkeit minimiert. Problem: Es könnte lokale Umwege geben.

Page 6

stellen wir ein drittes Kriterium: lokaler optimumality: Jede kurze subpath muss ein kürzester Weg sein.