Description
Q1. In this question, students are required to store the matrix representation of graph in the
file Lab9_input.txt and find shortest paths to all vertices in the given graph. The graph may
contain negative weight edges. Solve the question using Floyd Warshall algorithm and find
iteration used in convergence.
Example: Case 1:
number of vertices=8
number of edges=9
Information of all edges(source, destination, weight)
1 2 8
2 3 7
2 4 3
3 5 5
3 6 2
4 7 -4
4 8 6
5 7 -3
6 8 9
Expected Result:
The all pairs shortest distance matrix is
1 2 3 4 5 6 7 8
_______________________________________________________
1 | 0 8 15 11 20 17 7 17
2 | INF 0 7 3 12 9 -1 9
3 | INF INF 0 INF 5 2 2 11
4 | INF INF INF 0 INF INF -4 6
5 | INF INF INF INF 0 INF -3 INF
6 | INF INF INF INF INF 0 INF 9
7 | INF INF INF INF INF INF 0 INF
8 | INF INF INF INF INF INF INF 0
Case-2
number of vertices=4
number of edges=8
Information of all edges(source, destination, weight)
1 2 8
2 3 7
3 4 6
4 1 5
1 4 4
4 3 3
3 2 2
2 1 1
Expected Result:
The all pairs shortest distance matrix is
1 2 3 4
_______________________________
1 | 0 8 7 4
2 | 1 0 7 5
3 | 3 2 0 6
4 | 5 5 3 0
Q2. In this question students are required to find the shortest distance from a given source
vertex to all the vertices in the graph using Bellman Ford algorithm. Also find the number of
iterations used in the procedure. The query graph is given below: