lert dont submit AI generated answer. Write a program that reads a weighted graph. The program must print on the screen the distance matrix and the "PI" matrix of the shortest paths obtained by the Floyd-Warshall algorithm. Input: Receives n and m; n is the total number of vertices and m the total number of arcs. Next, m lines, each line with a trio of integers, corresponding to the beginning and end of the arc, followed by the weight of the arc. (Vertices are identified from 0 to n-1.) Output: Prints the distances and shortest paths obtained by the Floyd-Warshall algorithm. Exemple: Input: 5 9 0 1 3 0 2 8 0 4 -4 1 3 1 1 4 7 2 1 4 3 0 2 3 2 -5 4 3 6 Output: [[ 0 1 -3 2 -4] [ 3 0 -4 1 -1] [ 7 4 0 5 3] [ 2 -1 -5 0 -2] [ 8 5 1 6 0]] [[-1 2 3 4 0] [ 3 -1 3 1 0] [ 3 2 -1 1 0] [ 3 2 3 -1 0] [ 3 2 3 4 -1]]
lert dont submit AI generated answer.
Write a program that reads a weighted graph.
The program must print on the screen the distance matrix and the "PI" matrix of the shortest paths obtained by the Floyd-Warshall algorithm.
Input: Receives n and m; n is the total number of vertices and m the total number of arcs.
Next, m lines, each line with a trio of integers, corresponding to the beginning and end of the arc, followed by the weight of the arc.
(Vertices are identified from 0 to n-1.)
Output: Prints the distances and shortest paths obtained by the Floyd-Warshall algorithm.
Exemple:
Input:
5 9
0 1 3
0 2 8
0 4 -4
1 3 1
1 4 7
2 1 4
3 0 2
3 2 -5
4 3 6
Output:
[[ 0 1 -3 2 -4]
[ 3 0 -4 1 -1]
[ 7 4 0 5 3]
[ 2 -1 -5 0 -2]
[ 8 5 1 6 0]]
[[-1 2 3 4 0]
[ 3 -1 3 1 0]
[ 3 2 -1 1 0]
[ 3 2 3 -1 0]
[ 3 2 3 4 -1]]
Step by step
Solved in 3 steps with 2 images
