k-shortest (alternativa) algoritmo del percorso, implementazioni java

Question

Potresti raccomandare qualsiasi libreria java che implementa l'algoritmo k-shortest -> alla ricerca di modi alternativi, non l'unico più breve nella multigrafia diretta?

ho trovato solo JGraphT ma non v'è in realtà bug (che ho presentato), ma ci vorrà un sacco di tempo per risolvere il problema credo, ci sono altre implementazioni disponibili? Tranne JGraphT ho trovato solo piccoli progetti one-man:/

O sarebbe difficile modificare Disjktra percorso più breve alg per mostrare percorsi alternativi?

Grazie

Answer 1

2 possibili opzioni:

Opzione 1. La class KshortestPath da the MascOpt Package è una buona opzione per un Implementazione di Java dei percorsi più brevi.

Opzione 2. È inoltre possibile provare questo da code.google.com Questo sembra essere lo sforzo di una persona, ma la cosa buona è che l'algoritmo è condivisa:. Ranking di Yen - i dettagli sono qui (http://www.ohloh.net/p/k-shortest-paths)

Nota: Trovare i percorsi più brevi tra tutte le coppie di nodi in un dato grafico è un problema diverso. Vedi questa domanda SO su Dijkstra vs. Floyd-Warshall.

Si noti inoltre che k-shortest paths per i grafici ricchi tendono ad essere lievi variazioni del percorso più corto (Dijkstra) - percorsi alternativi tra i vertici sul percorso più breve con costi leggermente superiori.

So che l'OP ha richiesto le implementazioni Java, ma se le persone hanno una scelta e R è un'opzione, quindi lo kBestShortestPathspackage da CRAN è un'opzione molto buona.

Spero che questo aiuti.

Answer 2

c'è stata una richiesta di simile prima, ma alla ricerca di tutti i percorsi sul StackOverflow. Find all paths in a graph with DFS

Spero che questo aiuti, è stato risposto, ma non con la soluzione esatta, ma più di una guida

Answer 3

La ricerca dei percorsi k più brevi è correlata ma non lo stesso problema dei percorsi alternativi. Buoni percorsi alternativi sono più complicati. Have a read dove altri approcci simili sono descritti:

• k-Percorso Minimo
• Pareto ottimalità
• metodo Interiore
• approccio penali

Il metodo plateau è un po 'illustrata here.

Se è possibile per voi di leggere tedesco poi this lecture is nice:

• esempioottimizzazione per quanto riguarda il tempo o la distanza => problema: interessanti le alternative mancano
• percorsi dijunct => stesso problema
• k-percorsi più brevi => problema: la vera alternativa non è probabilmente sotto i primi 1000 percorsi

Page 5

Quindi l'intuizione ci dice: un'alternativa dovrebbe avere distanza o tempo quasi identici. ma dovrebbe essere diverso significativo. quindi la prima idea: trovare un percorso che riduce lunghezza e somiglianza. Problema: potrebbero esserci deviazioni locali.

Page 6

introduciamo un terzo criterio: optimumality locale: ogni breve sottotracciato deve essere un percorso più breve.