k-kürzeste (alternative) path-Algorithmus, java-Implementierungen

Könnten Sie empfehlen, alle java-Bibliothek implementiert die k-kürzesten Algorithmus -> Suche nach alternativen Möglichkeiten, nicht nur die kürzeste in der Regie multigraph ?

Fand ich nur, JGraphT, aber es gibt tatsächlich Fehler (die ich habe), aber es wird viel Zeit nehmen, um es zu beheben, ich denke,, gibt es irgendwelche anderen verfügbaren Implementierungen ? Außer JGraphT fand ich nur, kleinen ein-Mann-Projekte :/

ODER wäre schwer zu ändern Disjktra kürzesten Pfad alg zeigen alternative Wege ?

Dank

  • Sind Sie interessiert k-disjunkte kürzeste Kante oder Knoten-disjunkten Pfaden? Zum ersten, Blick in min-cost-max-flow algorithmen.
InformationsquelleAutor Martin V. | 2012-10-07
  1. 5

    2 Mögliche Optionen:

    Option 1. Die class KshortestPath aus die MascOpt Paket ist eine gute option für eine Java-Implementierung der k-kürzesten Wege.

    Option 2. Sie können auch versuchen, diese von code.google.com
    Dies scheint zu sein, ein eine person die Mühe, aber das gute daran ist, dass der Algorithmus wird geteilt: Yen-Ranking - die details sind hier.(http://www.ohloh.net/p/k-shortest-paths)

    Hinweis: Finden der kürzesten Wege zwischen allen Paaren von Knoten in einem gegebenen Graphen ist ein anderes problem. Finden Sie diese Frage ALSO auf Dijkstra vs. Floyd-Warshall.

    Beachten Sie auch, dass k-shortest paths für reiche Diagramme neigen dazu, leichte Abweichungen von der (Dijkstra) shortest-path - alternative Wege zwischen Scheitelpunkten auf dem kürzesten Weg mit etwas höheren Kosten.

    Ich weiß, der OP fragte, für Java-Implementierungen, aber wenn die Leute eine Wahl haben, und R ist eine option, dann die kBestShortestPaths Paket von CRAN ist eine sehr gute option.

    Hoffe, das hilft.

    • Ich habe gerade versucht Option 2: Yen-Algorithmus, und es wirkte Wunder! Die Ausführungszeit für einen Graphen mit ~400 nodes ~1000 links ging von 3000 ms (für JGrapht Umsetzung) 0,3 ms für die Yen-Algorithmus Implementierung. Ja, 3000 -> 0.3. Es ist kein Tippfehler.
    InformationsquelleAutor Ram Narasimhan
  2. 2

    Finden der k-kürzesten Wege verbunden ist, aber nicht genau das gleiche problem wie alternative Pfade. Gute alternativen Wege sind komplizierter. Gelesen zu haben , wo auch andere ähnliche Ansätze werden skizziert:

    • k-Kürzesten Wege
    • Pareto-Optimalität
    • Plateau-Methode
    • Strafe Ansatz

    Die plateau-Methode ist ein bit dargestellt hier.

    Wenn es möglich ist, für Sie auf Deutsch Lesen dann dieser Vortrag ist schön:

    • z.B. die Optimierung hinsichtlich Zeit oder Entfernung => problem: interessante alternativen fehlen
    • dijunct Pfade => gleichen problem
    • k-kürzesten Wege => problem: die echte alternative wahrscheinlich NICHT unter den ersten 1000 Wege

    Seite 5

    Also intuition sagt uns: eine alternative zu haben, fast identisch sind Distanz oder Zeit. sollte aber signifikanten Unterschied. also die erste Idee: einen Weg finden, die minizes Länge UND ähnlichkeit. Problem: es könnte sein, lokale Umwege.

    Seite 6

    stellen wir ein 3. Kriterium: lokalen optimumality: jeder kurze Unterpfad werden muss, um einen kürzesten Weg.

    InformationsquelleAutor Karussell
  3. 0

    Es wurde eine ähnliche Anfrage vor, aber ein Blick für alle Wege auf StackOverflow.
    Finden Sie alle Pfade in einem Graphen mit DFS

    Hoffe, das hilft, es wurde beantwortet, aber nicht mit der exakten Lösung, sondern eher ein Leitfaden

    InformationsquelleAutor Gigaquad
Schreibe einen Kommentar