KTH Camino más corto

Question

¿Alguien sabe cómo puedo escribir un algoritmo de gráfico de programación (el código C ++ sería genial) que encuentre la ruta más corta de KTH para un conjunto dado de nodos y bordes en un gráfico cíclico?

Por ejemplo, la ruta más corta (que podría ser encontrada por Dijkstra o Bellman Ford) se considera la primera ruta más corta. Ahora el segundo camino más corto es el más corto que viene después del primer camino más corto. Ahora quiero que el algoritmo encuentre la ruta más corta de KTH. Se le da la cantidad de nodos, bordes y el conjunto de bordes, como el siguiente:

Número de nodos: 5
Número de bordes: 6
Bordes:
0 1
0 2
1 2
2 3
3 1
1 4
Nodo de origen: 0
Nodo de destino: 4

"Tenga en cuenta que este gráfico contiene un ciclo" gracias.

Answer 1

Utilizar una búsqueda de costos uniformes algoritmo. Donde la wikipedia dice "solución de retorno", no renuncie y return Pero agregue el resultado a alguna lista hasta que esa lista contenga k caminos. los k'El elemento de la lista (contando desde 1) será el k'El camino más corto.

No mantenga un conjunto "cerrado"/"explorado" o este algoritmo no funcionará correctamente.