Due: 6th week (submission through moodle before sessional class)
Input: First line and second line of input file will contain the number of vertices, n and number of edges, m respectively followed by m lines each containing source, destination and weight of an edge of the directed graph.
For example:
Fig.: Input Graph
Input:
5
8
1 3 6
1 4 3
2 1 3
3 4 2
4 2 1
4 3 1
5 2 4
5 4 2
Section B1
Implement Floyd-Warshall algorithm for solving the all pair shortest-paths problem in the general case in which edge weights may be negative. Consider that there is no negative cycle. You need to calculate shortest paths for all pairs of vertices. Your algorithm should run in time O(V3).
Output:
Initial graph:
0
∞
6
3
∞
3
0
∞
∞
∞
∞
∞
0
2
∞
∞
1
1
0
∞
∞
4
∞
2
0
All pair shortest paths:
0
4
4
3
∞
3
0
7
6
∞
6
3
0
2
∞
4
1
1
0
∞
6
3
3
2
0
Predecessor Matrix:
∞
4
4
1
∞
2
∞
4
1
∞
2
4
∞
3
∞
2
4
4
∞
∞
2
4
4
5
∞
Section A1
Implement Floyd-Warshall algorithm for solving the all pair shortest-paths problem in the general case in which edge weights may be negative. Consider that there is no negative cycle. You need to calculate shortest paths for all pairs of vertices. Your algorithm should run in time O(V3) and should optimize the space requirement.
Output:
Initial graph:
0
∞
6
3
∞
3
0
∞
∞
∞
∞
∞
0
2
∞
∞
1
1
0
∞
∞
4
∞
2
0
All pair shortest paths:
0
4
4
3
∞
3
0
7
6
∞
6
3
0
2
∞
4
1
1
0
∞
6
3
3
2
0
Predecessor Matrix:
∞
4
4
1
∞
2
∞
4
1
∞
2
4
∞
3
∞
2
4
4
∞
∞
2
4
4
5
∞
Section B2
Implement Floyd-Warshall algorithm for solving the all pair shortest-paths problem in the general case in which edge weights may be negative. Consider that there is no negative cycle. You need to calculate shortest paths for all pairs of vertices. Your algorithm should run in time O(V3) and should optimize the space requirement.
Output:
Initial graph:
0
∞
6
3
∞
3
0
∞
∞
∞
∞
∞
0
2
∞
∞
1
1
0
∞
∞
4
∞
2
0
All pair shortest paths:
0
4
4
3
∞
3
0
7
6
∞
6
3
0
2
∞
4
1
1
0
∞
6
3
3
2
0
Predecessor Matrix:
∞
4
4
1
∞
2
∞
4
1
∞
2
4
∞
3
∞
2
4
4
∞
∞
2
4
4
5
∞
Section A2
Implement Floyd-Warshall algorithm for solving the all pair shortest-paths problem in the general case in which edge weights may be negative. Consider that there can be negative cycle. You need to calculate shortest paths for all pairs of vertices. Your algorithm should run in time O(V3) and should optimize the space requirement. Also detect whether the graph contains any negative cycle.
Output:
Initial graph:
0
∞
6
3
∞
3
0
∞
∞
∞
∞
∞
0
2
∞
∞
1
1
0
∞
∞
4
∞
2
0
All pair shortest paths:
0
4
4
3
∞
3
0
7
6
∞
6
3
0
2
∞
4
1
1
0
∞
6
3
3
2
0
Predecessor Matrix:
∞
4
4
1
∞
2
∞
4
1
∞
2
4
∞
3
∞
2
4
4
∞
∞
2
4
4
5
∞
Negative cycle? No
