Floyd-Warshall

propuesto por josejuan

Dada una matriz de costes, implementar el algoritmo Floyd-Warshall.

Enunciado
Habría que implementar la carga y cálculo de la matriz de distancias mínimas y luego una función que calcule la ruta más corta (si existe) entre dos nodos cualesquiera.

Un ejemplo de matriz (con costes negativos) representando un grafo de 1000 nodos podría ser

https://gist.github.com/4632581

Que está en el siguiente formato:
  • La primera línea contiene una cabecera y el resto de línea son relaciones.
  • La cabecera tiene dos campos: el nº de nodos en el grafo y la suma de costes (finitos).
  • Una relación tiene tres campos: el índice de un nodo A, el índice del otro nodo B y el coste.
  • Las relaciones entre pares de nodos (A, B) que no se indican, es porque tienen coste 0 si A=B o bien porque tienen coste infinito si A<>B.

Por ejemplo, la matriz de ejemplo que hay en [] se escribiría en este mismo formato como:

6 74
1 4 1
3 6 1
4 1 1
6 3 1
1 2 3
2 1 3
4 6 4
6 4 4
1 3 5
3 1 5
3 4 7
3 5 7
4 3 7
5 3 7
2 5 9
5 2 9

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

3 Soluciones

Dar mi solución

0votos
Floyd-Warshall en Haskell
por

jneira

hace 6 años

Version mas eficiente que logre implementar en haskell (o sea fracaso total ya que tarda horas en resolver un grafo de 1000 nodos): puramente imperativa usando Data.Array.IO, usando un array de una dimension calculando al vuelo los indices y usando recursion en lugar de forM

0votos
Floyd-Warshall en Haskell
por

jneira

hace 6 años

La solucion devuelve el path mas corto de todos los posibles si no hay un ciclo negativo si lo hay devuelve Nothing. Es puramente funcional con trampa: Data.Array.Diff usa unsafePeformIO internamente para conseguir que modificar el array sea O(1)

Dar mi solución