Module: algoritmo de floyd

Se le proporciona un gráfico ponderado dirigido. Utilizando su matriz de adyacencia, debe determinar para cada par de vértices si existe o no un camino más corto entre ellos.

 

Comentario: Es posible que la ruta más corta no exista por dos motivos:

La primera línea del archivo de entrada contiene un solo número: N (1 <=N <=100) — el número de vértices del gráfico. Las siguientes N líneas contienen N números cada una — matriz de adyacencia del gráfico (el j-ésimo número en la i-ésima línea corresponde al peso de la arista desde el vértice i hasta el vértice j): el número 0 significa que no hay arista, y cualquier otro número — la presencia de un borde del peso correspondiente. Todos los números de módulo no superan 100.

 

Imprime N líneas de N números. El j-ésimo número en la i-ésima línea debe corresponder al camino más corto del vértice i al vértice j. El número debe ser 0 si no hay ruta, 1 si hay una ruta más corta y 2 si hay rutas, pero hay rutas de peso arbitrariamente pequeño.

Ejemplos

#	Entrada	Salida
1	5 0 1 2 0 0 1 0 3 0 0 2 3 0 0 0 0 0 0 0 -1 0 0 0 -1 0	1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 2 2 0 0 0 2 2