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
Bennett University Greater Noida
Department of CSE
Subject Lab: Algorithms & Complexity Lab Duration: 10:40-12:35
Lab Code: ECSE202L Max Marks: 10
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:
Bennett University Greater Noida
Department of CSE
Subject Lab: Algorithms & Complexity Lab Duration: 10:40-12:35
Lab Code: ECSE202L Max Marks: 10
