Design and implement Floyd’s algorithm to compute all-pair shortest paths in any
ID: 3593344 • Letter: D
Question
Design and implement Floyd’s algorithm to compute all-pair shortest paths in any given graph using
An adjacency matrix using a one-dimensional array for storing only the elements of the lower triangle in the adjacency matrix.[Using C programming]
The input to program must be connected, undirected, and weighted graphs. The programs must be able to find shortest paths on two types of connected, undirected, and weighted graphs: complete graph (a graph with a link between every pair of nodes) and sparse graph (a graph with exactly n-1 links). To prepare graphs as inputs must include these additional programs (functions) as follows:
1. Random. A program to randomly generate a number between 1 and n. You can use a random number generator function in the libraries of your programming language or write your own function.
2. Complete. A program that can create an adjacency matrix for an undirected complete graph with any given size n.
3. Sparse. A program that can create an adjacency matrix for an undirected sparse graph with any given size n. The Sparse program must use the Random program (number 1 in this list) to determine all the links (n-1) in the sparse graph.
4. Weight. To include weights on the links of the undirected complete graphs (generated by the Complete program, number 2 in this list) and on the links of the undirected sparse graphs (generated by the Sparse program, number 3 in this list), use the Random program (number 1 in this list) to generate positive numbers as weights
Please provide the output for test cases and also the graphs
TEST CASE:
Test case:
adj-test case-1
. . . 29 . . . .
. . . . . 11 11 .
. . . 12 . 5 5 .
29 . 12 . 5 . 13 .
. . . 5 . . 7 11
. 11 5 . . . . 17
. 11 5 13 7 . . .
. . . . 11 17 . .
adj-test case-2
. . . 29 . . . .
. . . . . 11 11 .
. . . 12 . 5 5 .
29 . 12 . 5 . 13 .
. . . 5 . . 7 11
. 11 5 . . . . 17
. 11 5 13 7 . . .
. . . . 11 17 . .
10 15 Shortest path between v2 - v8: The distance is: 35 The path is: v2->v3->v6->v9->v8 13 25 25 17 28 25 14 18 Shortest path between v12-v10: The distance is:? The path is:? 14 12 29 13 16 12Explanation / Answer
// C Program for Floyd Warshall Algorithm
#include<stdio.h>
// Number of vertices in the graph
#define V 4
/* Define Infinite as a large enough value. This value will be used
for vertices not connected to each other */
#define INF 99999
// A function to print the solution matrix
void printSolution(int dist[][V]);
// Solves the all-pairs shortest path problem using Floyd Warshall algorithm
void floydWarshall (int graph[][V])
{
/* dist[][] will be the output matrix that will finally have the shortest
distances between every pair of vertices */
int dist[V][V], i, j, k;
/* Initialize the solution matrix same as input graph matrix. Or
we can say the initial values of shortest distances are based
on shortest paths considering no intermediate vertex. */
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
/* Add all vertices one by one to the set of intermediate vertices.
---> Before start of a iteration, we have shortest distances between all
pairs of vertices such that the shortest distances consider only the
vertices in set {0, 1, 2, .. k-1} as intermediate vertices.
----> After the end of a iteration, vertex no. k is added to the set of
intermediate vertices and the set becomes {0, 1, 2, .. k} */
for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// Print the shortest distance matrix
printSolution(dist);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.