Ipol:Modulo6b

Algoritmo de Dijkstra

Pasos

• leer un grafo de disco en formato de matriz de adyacencia, igual que en el ejercicio anterior.
• leer los nodos inicial y final de la entrada estándar
• calcular las distancias del nodo inicial al todos los nodos del grafo utilizando el algoritmo de Dijkstra
• calcular el camino mínimo (y su costo) entre los nodos inicial y final
• Se deberá guardar como salida un archivo con el camino con el siguiente formato

<bash> 3 #número de nodos A #nodos del camino en orden (comenzando con el inicial) G Z 30 #costo total del camino </bash>

Pruebas

Probar con los siguientes grafos: grafos_dijkstra.zip

Hay dos grafos, uno sencillo de pocos nodos (Fig. 1), y un k1000 (grafo completo de 1000 nodos). Se recomienda testear el algoritmo con el primer grafo y luego probar la eficiencia computacional con el grafo completo.

En las matrices de adyacencia, un valor infinito es desconectado y un valor finito es conectado, donde el valor representa el costo. Como no se puede representar infinito, usamos el siguiente número: 2147483647

Fig. 1: Grafo de ejemplo.

Informe

• comparar eficiencia en ciclos con y sin heap (puede ser util usar un grafo grande)
• comparar eficiencia teórica con la obtenida en la práctica (ciclos en función de n)