Program 14 : Floyd's Algorithm

Develop a program to Implement Floyd’s Algorithm for a graph of n nodes.

Floyd’s Algorithm

The Floyd–Warshall Algorithm for computing the shortest paths between all pairs of vertices in a weighted graph.

#include <stdio.h>

#define MAX 100
#define INF 99999  
// Represents infinity (no direct path)

// Floyd's Algorithm to compute shortest distances
void floydWarshall(int graph[MAX][MAX], int n) {
    int dist[MAX][MAX];
    int i, j, k;

    // Initialize distance matrix same as input graph
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            dist[i][j] = graph[i][j];

    // Update distances using intermediate nodes
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF &&
                    dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // Display the shortest distance matrix
    printf("Shortest distances between every pair of vertices:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (dist[i][j] == INF)
                printf("INF ");
            else
                printf("%3d ", dist[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[MAX][MAX];
    int n;

    printf("Enter the number of nodes: ");
    scanf("%d", &n);

    printf("Enter the adjacency matrix (use 99999 for no direct edge):\n");
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &graph[i][j]);

    floydWarshall(graph, n);

    return 0;
}

---

Floyd's Algorithm

Floyd’s Algorithm computes the shortest distance between every pair of vertices.

Core Idea:

• For each pair (i, j), check if going through an intermediate node k results in a shorter path.

• The matrix is updated as:

if (dist[i][j] > dist[i][k] + dist[k][j])
	dist[i][j] = dist[i][k] + dist[k][j];

---

Input Format

• Input is given as an adjacency matrix.

• Use a large number (like 99999) to represent "no edge" (infinity).

Example Input:

0 3 99999 7
8 0 2 99999
5 99999 0 1
2 99999 99999 0

Output:

Shortest distances between every pair of vertices:
  0   3   5   6
  5   0   2   3
  3   6   0   1
  2   5   7   0

---

Let me know if you'd like:

• To track the intermediate matrices step by step

• A version with path reconstruction

• Or if you want to compare it with Dijkstra’s algorithm for single-source shortest paths