Algoritmo de ruta k-shortest (alternativo), implementaciones Java

Question

¿Podría recomendar cualquier biblioteca java que implemente el algoritmo k-shortest -> buscando formas alternativas, no la más corta en multigrafo dirigido?

Encontré solo JGraphT pero en realidad hay un error (que presenté) pero tomará mucho tiempo arreglarlo, supongo, ¿hay otras implementaciones disponibles? Excepto JGraphT, solo encontré pequeños proyectos de un solo hombre:/

O sería difícil modificar Disjktra shortest path alg para mostrar rutas alternativas?

Gracias

Answer 1

2 opciones posibles:

Opción 1. El class KshortestPath de the MascOpt Package es una buena opción para una Implementación de Java de las rutas k-más cortas.

Opción 2. También puede probar esto desde code.google.com Esto parece ser un esfuerzo de una sola persona, pero lo bueno es que el algoritmo es compartida:. Ranking de Yen - los detalles aquí (http://www.ohloh.net/p/k-shortest-paths)

Nota: Encontrar las rutas más cortas entre todos los pares de nodos en un gráfico dado es un problema diferente. Vea esta pregunta SO en Dijkstra vs. Floyd-Warshall.

También tenga en cuenta que k-shortest paths para gráficos ricos tienden a ser ligeras variaciones de la ruta más corta (Dijkstra) - rutas alternativas entre vértices en el camino más corto con costos ligeramente más altos.

Sé que OP solicitó las implementaciones de Java, pero si las personas tienen otra opción y R es una opción, entonces el kBestShortestPathspackage de CRAN es una muy buena opción también.

Espero que ayude.

Answer 2

Ha habido una petición similar antes, pero en busca de todas las rutas en StackOverflow. Find all paths in a graph with DFS

Espero que esto ayude, que fue respondida, pero no con la solución exacta, sino más bien una guía

Answer 3

Encontrar las rutas k-más cortas está relacionado pero no con el mismo problema que las rutas alternativas. Los buenos caminos alternativos son más complicados. Have a read donde se describen otros enfoques similares:

• k-rutas más cortas de
• óptimo de Pareto
• método meseta
• enfoque Pena

El método de la meseta es un poco ilustrado here.

Si es posible que usted pueda leer en alemán y luego this lecture is nice:

• por ejemplo,optimización en cuanto al tiempo o la distancia => problema: interesantes alternativas faltan
• caminos dijunct => mismo problema
• k-caminos más cortos => problema: la alternativa real es probablemente no bajo los 1000 primeros caminos

Página 5

Por lo que la intuición nos dice: una alternativa debe tener una distancia o tiempo casi idénticos. pero debe ser significativamente diferente. entonces la primera idea: encontrar un camino que minimice la longitud Y la similitud. Problema: podría haber desvíos locales.

Página 6

se introduce una tercera criterio: optimumality locales: cada subtrazado corto tiene que ser un camino más corto.