Core Principles of Floyd's Algorithm

Floyd's algorithm provides an elegant solution for finding shortest paths in graphs using dynamic programming. The method operates on two primary matrices:

• Distance Matrix (D): Stores minimum path weights between vertices
• Predecessor Matrix (P): Records intermediate vertices in shortest paths

The algorithm's fundamental operation compares paths through intermediate vertices using the relation:

D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Algorithm Execution Process

Consider a graph with vertices labeled A-G (indices 0-6):

1. Initialize matrices with direct edge weights
2. Iterate through intermediate vertices:
   • When k=0 (A), path B→G updates from ∞ to 26 via A
   • When k=1 (B), path A→C updates from ∞ to 22 via B
3. Continue until all intermediate vertices are processed

C Implemantation

#include <stdio.h>
#define MAX_VERTICES 10
#define INF 9999

typedef struct {
    int vertex_count;
    int edge_count;
    int weights[MAX_VERTICES][MAX_VERTICES];
} Graph;

void floyd(Graph *g, int dist[MAX_VERTICES][MAX_VERTICES], 
           int pred[MAX_VERTICES][MAX_VERTICES]) {
    for (int i = 0; i < g->vertex_count; i++) {
        for (int j = 0; j < g->vertex_count; j++) {
            dist[i][j] = g->weights[i][j];
            pred[i][j] = j;
        }
    }

    for (int k = 0; k < g->vertex_count; k++) {
        for (int i = 0; i < g->vertex_count; i++) {
            for (int j = 0; j < g->vertex_count; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pred[i][j] = pred[i][k];
                }
            }
        }
    }
}

void trace_path(int pred[MAX_VERTICES][MAX_VERTICES], 
                int start, int end) {
    printf("Path: %d", start);
    int current = start;
    while (current != end) {
        current = pred[current][end];
        printf(" → %d", current);
    }
}

int main() {
    Graph g;
    printf("Enter vertex count: ");
    scanf("%d", &g.vertex_count);
    
    printf("Enter adjacency matrix:\n");
    for (int i = 0; i < g.vertex_count; i++) {
        for (int j = 0; j < g.vertex_count; j++) {
            scanf("%d", &g.weights[i][j]);
        }
    }

    int dist[MAX_VERTICES][MAX_VERTICES];
    int pred[MAX_VERTICES][MAX_VERTICES];
    
    floyd(&g, dist, pred);
    trace_path(pred, 0, 3);
}

Path Reconstruction

To retrieve the shortest path between vertices:

1. Start at origin vertex
2. Follow predecessor matrix entries
3. Terminate at destination vertex

Example output for path from A(0) to D(3):

Path: 0 → 1 → 3