Sample Output

Enter the number of vertices: 4
Enter number of edges: 5
Enter end vertices of edge 1
1
2
Enter the weight of edge 1
2
Enter end vertices of edge 2
1
3
Enter the weight of edge 2
5
Enter end vertices of edge 3
2
4
Enter the weight of edge 3
3
Enter end vertices of edge 4
3
4
Enter the weight of edge 4
6
Enter end vertices of edge 5
1
4
Enter the weight of edge 5
4

Shortest distance path is:
1 - 1 = 0
1 - 2 = 2
1 - 3 = 5
1 - 4 = 4
2 - 1 = 2
2 - 2 = 0
2 - 3 = 7
2 - 4 = 3
3 - 1 = 5
3 - 2 = 7
3 - 3 = 0
3 - 4 = 6
4 - 1 = 4
4 - 2 = 3
4 - 3 = 6
4 - 4 = 0

---

Step-by-Step Output Explanation

1. Input Process

• The program asks for the number of vertices (v) and edges (e) in the graph.
• Then, it prompts the user to enter the vertices connected by each edge and the corresponding weights.

In this example:

• Number of vertices (v): 4
• Number of edges (e): 5

The edges entered are:

1. Edge between vertex 1 and vertex 2 with weight 2
2. Edge between vertex 1 and vertex 3 with weight 5
3. Edge between vertex 2 and vertex 4 with weight 3
4. Edge between vertex 3 and vertex 4 with weight 6
5. Edge between vertex 1 and vertex 4 with weight 4

2. Initial Matrix Setup

• The adjacency matrix g is initialized with 32767 (representing infinity) for all vertex pairs, except for the diagonal, which is set to 0 (the distance from a vertex to itself).

The initial adjacency matrix looks like this:

	1	2	3	4
1	0	∞	∞	∞
2	∞	0	∞	∞
3	∞	∞	0	∞
4	∞	∞	∞	0

3. Edge Weights Assignment

• Each edge entered updates the adjacency matrix with the given weights. The graph is undirected, so we set both g[a][b] and g[b][a] to the same weight.

After inputting the edges, the adjacency matrix becomes:

	1	2	3	4
1	0	2	5	4
2	2	0	∞	3
3	5	∞	0	6
4	4	3	6	0

4. Floyd-Warshall Algorithm Execution

The Floyd-Warshall algorithm works by updating the distance between all pairs of vertices (i, j) using an intermediate vertex k.

• The algorithm iterates over each vertex k and checks if the path from vertex i to vertex j through vertex k is shorter than the current known path.
• The update rule is: g[i][j]=min⁡(g[i][j],g[i][k]+g[k][j])

We perform this update for each intermediate vertex k from 1 to v. Let’s go step by step:

Iteration 1: k = 1

• For each pair (i, j), check if the path through vertex 1 provides a shorter distance.

After updating, the matrix looks like:

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

Iteration 2: k = 2

• For each pair (i, j), check if the path through vertex 2 provides a shorter distance.

After updating, the matrix looks like:

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

(No changes were made in this iteration.)

Iteration 3: k = 3

• For each pair (i, j), check if the path through vertex 3 provides a shorter distance.

After updating, the matrix looks like:

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

(No changes were made in this iteration.)

Iteration 4: k = 4

• For each pair (i, j), check if the path through vertex 4 provides a shorter distance.

After updating, the matrix looks like:

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

(No changes were made in this iteration.)

5. Final Output Matrix

After completing all iterations, the matrix g[i][j] contains the shortest distances between each pair of vertices.

Here is the final shortest distance matrix:

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

Interpretation of the Final Results

1. 1 to 2: The shortest path is the direct edge with weight 2.
2. 1 to 3: The shortest path is the direct edge with weight 5.
3. 1 to 4: The shortest path is the direct edge with weight 4.
4. 2 to 1: The shortest path is the direct edge with weight 2.
5. 2 to 3: The shortest path is via vertex 1 (2 -> 1 -> 3) with a total weight of 7.
6. 2 to 4: The shortest path is the direct edge with weight 3.
7. 3 to 1: The shortest path is via vertex 4 (3 -> 4 -> 1) with a total weight of 5.
8. 3 to 2: The shortest path is via vertex 4 (3 -> 4 -> 2) with a total weight of 7.
9. 3 to 4: The shortest path is the direct edge with weight 6.
10. 4 to 1: The shortest path is the direct edge with weight 4.
11. 4 to 2: The shortest path is the direct edge with weight 3.
12. 4 to 3: The shortest path is the direct edge with weight 6.