[go: up one dir, main page]
Scribd
Upload
23 views3 pages

04 - 11 - 2024 Floyd Warshall 2205317

KIIT

Uploaded by

Rudroprasad Bandyopadhyay 2
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
23 views3 pages

04 - 11 - 2024 Floyd Warshall 2205317

KIIT

Uploaded by

Rudroprasad Bandyopadhyay 2
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Source Code:-

#include <stdio.h>

#define INF 99999 // Representing infinity for no direct edge

void floydWarshall(int V, int graph[V][V], int dist[V][V], int pred[V][V])


{
// Initialize the distance and predecessor matrices
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (graph[i][j] != INF && i != j)
{
dist[i][j] = graph[i][j];
pred[i][j] = i;
}
else
{
dist[i][j] = graph[i][j];
pred[i][j] = -1;
}
}
dist[i][i] = 0; // Distance to self is zero
}

// Floyd-Warshall algorithm with predecessor update


for (int k = 0; k < V; k++)
{
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
pred[i][j] = pred[k][j];
}
}
}
}
}
void printMatrix(int V, int matrix[V][V], int isDistance)
{
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (matrix[i][j] == INF)
{
printf("%4s", "INF");
}
else if (isDistance)
{
printf("%4d", matrix[i][j]);
}
else
{
printf("%4d", matrix[i][j]);
}
}
printf("\n");
}
}

int main()
{
int V = 5;

// Adjacency matrix representation of the graph


int graph[5][5] = {
{0, 3, 8, INF, -4},
{INF, 0, INF, 1, 7},
{INF, 4, 0, INF, INF},
{2, INF, -5, 0, INF},
{INF, INF, INF, 6, 0}};

int dist[5][5], pred[5][5];

// Run Floyd-Warshall algorithm


floydWarshall(V, graph, dist, pred);

// Print the shortest distance matrix


printf("Shortest path distance matrix:\n");
printMatrix(V, dist, 1);
// Print the predecessor matrix
printf("\nPredecessor matrix:\n");
printMatrix(V, pred, 0);

return 0;
}

Output:-

Shortest path distance matrix:


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

Predecessor matrix:
-1 2 3 4 0
3 -1 3 1 0
3 2 -1 1 0
3 2 3 -1 0
3 2 3 4 -1

You might also like