Scribd
Upload
20 views

DAA-Program 7-1

Jsjaja

Uploaded by

works8606
Copyright
© © All Rights Reserved
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
20 views

DAA-Program 7-1

Jsjaja

Uploaded by

works8606
Copyright
© © All Rights Reserved
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Program #7

Objective: Write a program to implement All-Pair-Shortest-Path using Floyd-Warshall’s


algorithm.
Software required: Borland C /Tubo C / GCC
Description:
The Floyd-Warshall’s algorithm is a graph algorithm that is deployed to find the shortest path
between all the vertices present in a weighted graph. This algorithm is different from other
shortest path algorithms; to describe it simply, this algorithm uses each vertex in the graph as
a pivot to check if it provides the shortest way to travel from one point to another.
Floyd-Warshall’s algorithm works on both directed and undirected weighted graphs unless
these graphs do not contain any negative cycles in them. By negative cycles, it is meant that
the sum of all the edges in the graph must not lead to a negative number.
Since, the algorithm deals with overlapping sub-problems – the path found by the vertices
acting as pivot are stored for solving the next steps – it uses the dynamic programming
approach.
Floyd-Warshall’s algorithm is one of the methods in All-pairs shortest path algorithms and it
is solved using the Adjacency Matrix representation of graphs.
Consider a graph, G = {V, E} where V is the set of all vertices present in the graph and E is the
set of all the edges in the graph. The graph, G, is represented in the form of an adjacency
matrix, A, that contains all the weights of every edge connecting two vertices.

Algorithm:
Step 1 − Construct an adjacency matrix A with all the costs of edges present in the graph. If
there is no path between two vertices, mark the value as ∞.
Step 2 − Derive another adjacency matrix A1 from A keeping the first row and first column of
the original adjacency matrix intact in A1. And for the remaining values, say A1[i,j],
if A[i,j]>A[i,k]+A[k,j] then replace A1[i,j] with A[i,k]+A[k,j]. Otherwise, do not change the
values. Here, in this step, k = 1 (first vertex acting as pivot).
Step 3 − Repeat Step 2 for all the vertices in the graph by changing the k value for every pivot
vertex until the final matrix is achieved.
Step 4 − The final adjacency matrix obtained is the final solution with all the shortest paths.

Floyd-Warshall(w, n){ // w: weights, n: number of vertices


for i = 1 to n do // initialize, D (0) = [wij]
for j = 1 to n do{
d[i, j] = w[i, j];
}
for k = 1 to n do // Compute D (k) from D (k-1)
for i = 1 to n do
for j = 1 to n do
if (d[i, k] + d[k, j] < d[i, j]){
d[i, j] = d[i, k] + d[k, j];
}
return d[1..n, 1..n];
}
Program:

Abhinav Singh (2105250100002.)


#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 dist[][V])
{
int i, j, k;

/* Add all vertices one by one to the set of intermediate vertices.


---> Before start of an 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 an 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);
}

/* A utility function to print solution */


void printSolution(int dist[][V])
{
printf(

Abhinav Singh (2105250100002.)


"The following matrix shows the shortest distances"
" between every pair of vertices \n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}

// driver's code
int main()
{
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5| |
| |1
\|/ |
(1)------->(2)
3 */
int graph[V][V] = { { 0, 5, INF, 10 },
{ INF, 0, 3, INF },
{ INF, INF, 0, 1 },
{ INF, INF, INF, 0 } };

// Function call
floydWarshall(graph);
return 0;
}

Output:

The following matrix shows the shortest distances between every pair of vertices
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0

Abhinav Singh (2105250100002.)

You might also like