## 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: