Algoritmo: buscar conexiones entre ciudades con un límite de cambios de tren

Question

¿Qué algoritmo utilizarías para crear una aplicación que proporcionara los datos apropiados (lista de ciudades, rutas de tren, estaciones de tren) capaz de devolver una lista de conexiones entre dos ciudades seleccionadas por el usuario? La aplicación tiene que elegir solo aquellas conexiones que caen dentro del límite de cambios de tren aceptados.

Ejemplo: Pregunto a la aplicación qué tren tomar si tengo que viajar de París a Moscú con un máx. 1 parada/cambio - la aplicación devuelve una ruta: Tren 1 (París-Berlín) -> Tren 2 (Berlín-> Moscú) (No existe conexión directa).

Ejemplo gráfico

http://i.imgur.com/KEJ3I.png

Si pido el sistema acerca de las posibles conexiones de Ciudad Un a Ciudad G puedo obtener una respuesta:

• línea marrón (0 interruptores = directo)
• Line Brown a Ciudad Línea B/naranja a Ciudad G (1 Interruptor)
• línea marrón a Ciudad Línea B/naranja a Ciudad del D/línea roja a G (2 Interruptor)
• ... todas las demás posibilidades

Y si la segunda y la tercera opción son más cortas que la primera, es la primera que debería tener prioridad (ya que no se requiere cambio de tren).

Answer 1

Suponiendo que lo único importante es "número de paradas/conmutadores", entonces el problema es encontrar la ruta más corta en un directed graph no ponderado.

El modelo gráfico es G = (V,E) donde V = {all possible stations} y E = { (u,v) | there is a train/route from station u to station v }
Nota: digamos que tiene un tren que comienza en A_0 y caminos a través de a_1, a_2, ... a_n: entonces E contendrá: (a_0,a_1),(a_0,a_2),..,(a_0,a_n) y también (a_1,a_2),(a_1,a_3),... formalmente: para cada i < j: (a_i, A_j) ∈ E.

BFS resuelve este problema, y ​​es a la vez complete [siempre encuentra una solución si hay uno] y optimal [encuentra el camino más corto].

Si los bordes [rutas] son ​​ponderados, en su lugar se necesitará algo como dijkstra's algorithm.

Si desea una lista de todas las rutas posibles , Iterative-Deepening DFS podrían utilizarse, sin mantener un conjunto visitado, e imprimir todos los caminos que se encuentran a la meta hasta la profundidad correspondiente. [BFS no puede devolver todas las rutas con el ejemplo de contador de una camarilla]

Answer 2

Creo que necesita calcular todos los pares de rutas más cortas. Compruebe http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm.