ECSE202L  Lab Assignment 9 solution

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