El problema del Rio Congo
- A lo largo del río Congo hay E embarcaderos a los que nombramos con los números enteros 1, 2, . . . , E.
- Es posible ir en canoa desde un embarcadero a cualquiera de los dos siguientes en la dirección de la corriente.
- No se puede navegar contra corriente, ni tampoco ir más allá del segundo embarcadero sin efectuar escala alguna.
- Problema: Dada una función de ponderación que asigna un coste (positivo) a cada arco, calcular el camino de menor coste del primer al último embarcadero y su coste.
Implementación
Para resolver el problema se lee el grafo de un fichero que se pasa como parámetro al ejecutable. Este fichero debe contener una matriz de adyacencia donde el valor será el coste de la arista que une dos nodos, tal y como se puede ver:
Presentación de la solución
Este proyecto contiene el código que resuelve el algoritmo y muestra la solución por pantalla. Para obtener esa solución utilizo dos métodos distintos, el de recomposición por punteros y de recomposición con postproceso.
En el descargable del proyecto he incluido además una pequeña memoria en la que se analizan los procesos y se muestran algunas trazas.
