Write the following complete C (or C++) programs.

1. 1. c to implement Floyds algorithm to solve the all-pairs shortest-paths problem, where the directed weighted connected graph has no negative-length cycle. [40 marks] 2. Dijkstra.c to implement Dijkstras algorithm to solve the single-source shortest-paths problem, where the directed weighted connected graph has no negative weight. 3. BellmanFord.c to implement Bellman and Fords algorithm to solve the single-source shortest-paths problem, where the directed weighted connected graph has no negative-length cycle. [30 marks]

• A graph is represented using an adjacency matrix (also called weight, cost, or length matrix).
• For the c program, you may use the following graph to test your program.
• The weight (cost, length) adjacency matrix of the graph is

	1	2	3			0	1	2
1	0	4	11		0	0	4	11
2	6	0	2		1	6	0	2
3	3		0		2	3		0

Given weight adjacency matrix Weight adjacency matrix stored in memory

(I = 99999 indicates )

A demonstrative output of the Floyd.c program is given below.

The weight matrix W is

0 4 11

6 0 2

3 I 0

D(1) is

0 4 11

6 0 2

3 7 0

D(2) is

0 4 6

6 0 2

3 7 0

D(3) is

0 4 6

5 0 2

3 7 0

The distance matrix D is

0 4 6

5 0 2

3 7 0

The Path matrix is

-1 -1 1

2 -1 -1

-1 0 -1

Path length = 4, Path from 1 to 2 is: 1 > 2

Path length = 6, Path from 1 to 3 is: 1 > 2 > 3

Path length = 5, Path from 2 to 1 is: 2 > 3 > 1

Path length = 2, Path from 2 to 3 is: 2 > 3

Path length = 3, Path from 3 to 1 is: 3 > 1

Path length = 7, Path from 3 to 2 is: 3 > 1 > 2

• For the c program, you may use the following graph to test your program.

• The cost (weight, length) adjacency matrix of the graph is

v0 v1 v2 v3 v4 v0 0 7 v1 3 0 4 v2 0 6 v3 2 5 0 v4 4 0

0 1 2 3 4 0 0 I I 7 I 1 3 0 4 I I 2 I I 0 I 6 3 I 2 5 0 I 4 I I I 4 0

Given cost adjacency matrix Cost adjacency matrix stored in memory

(I = 99999 indicates )

A demonstrative output of the Dijkstra.c program is given below.

The weight matrix W is

0 I I 7 I

3 0 4 I I

I I 0 I 6

I 2 5 0 I

I I I 4 0

1. dist[] and parent[] are
   • I I 7 I
   • -1 -1 0 -1
2. dist[] and parent[] are
   • 9 12 7 I
   • 3 3 0 -1
3. dist[] and parent[] are
   • 9 12 7 I
   • 3 3 0 -1
4. dist[] and parent[] are
   • 9 12 7 18

-1 3 3 0 2

The distance array dist[] is

0 9 12 7 18

The parent array parent[] is

-1 3 3 0 2

Path length = 9, Path from 0 to 1 is: 0 > 3 > 1

Path length = 12, Path from 0 to 2 is: 0 > 3 > 2

Path length = 7, Path from 0 to 3 is: 0 > 3 Path length = 18, Path from 0 to 4 is: 0 > 3 > 2 > 4

• For the c program, you may use the following graph to test your program.

• The cost (weight, length) adjacency matrix of the graph is

	1	2	3	4	5	6			0	1	2	3	4	5
1	0	2	4					0	0	2	4
2		0	-3	1	5			1		0	-3	1	5
3			0	-4	-2			2			0	-4	-2
4				0		8		3				0		8
5				4	0	6		4				4	0	6
6						0		5						0

Given cost adjacency matrix Cost adjacency matrix stored in memory

(I = 99999 indicates )

A demonstrative output of the BellmanFord.c program is given below.

The weight matrix W is

0 2 4 I I I

I 0 -3 1 5 I

I I 0 -4 -2 I

I I I 0 I 8

I I I 4 0 6 I I I I I 0 dist(1) is 0 2 4 I I I -1 1 1 -1 -1 -1 dist(2) is 0 2 -1 0 2 I -1 1 2 3 3 -1 dist(3) is 0 2 -1 -5 -3 8 -1 1 2 3 3 4

dist(4) is

0 2 -1 -5 -3 3

-1 1 2 3 3 4

dist(5) is

0 2 -1 -5 -3 3

-1 1 2 3 3 4

The distance array dist is

0 2 -1 -5 -3 3

The parent array is

-1 1 2 3 3 4

Path length = 2, Path from 1 to 2 is: 1 > 2

Path length = -1, Path from 1 to 3 is: 1 > 2 > 3

Path length = -5, Path from 1 to 4 is: 1 > 2 > 3 > 4

Path length = -3, Path from 1 to 5 is: 1 > 2 > 3 > 5

Path length = 3, Path from 1 to 6 is: 1 > 2 > 3 > 4 > 6