Sequential and Parallel Computing for All-Pairs Distance Computation

parallel_apsp.cpp

/*
How Parallel Computing Works for All-Pairs Distance Computation
(using Floyd–Warshall Algorithm with OpenMP)

Problem:
Given a weighted graph with V vertices, compute the shortest distance
between every pair of vertices.

We use the Floyd–Warshall algorithm:
for k = 0 to V-1
  for i = 0 to V-1
    for j = 0 to V-1
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

---------------------------------------------------
DEPENDENCY ANALYSIS (VERY IMPORTANT)
---------------------------------------------------
- The outer loop (k) CANNOT be parallelized
  → iteration k depends on results of k-1
- For a fixed k:
  - All (i, j) updates are independent
  - Therefore, loops over i and j CAN be parallelized

---------------------------------------------------
PARALLEL STRATEGY
---------------------------------------------------
1. Outer loop over k runs sequentially
2. For each k:
   - OpenMP parallelizes the nested (i, j) loops
3. Threads update different cells of the distance matrix
4. Barrier occurs implicitly at the end of each parallel region

This program compares:
- Sequential Floyd–Warshall
- Parallel Floyd–Warshall using OpenMP

Compile:
>>> g++ -fopenmp -O2 -o parallel_apsp parallel_apsp.cpp
Run:
>>> ./parallel_apsp
*/

#include <bits/stdc++.h>
#include <omp.h>
using namespace std;

const int INF = 1e9;

int main() {
    const int V = 2000;  // Number of vertices (keep moderate)
    
    vector<vector<int>> graph(V, vector<int>(V));
    vector<vector<int>> seq_dist, par_dist;

    // ---------------------------
    // Initialize Graph
    // ---------------------------

    srand(0);
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (i == j)
                graph[i][j] = 0;
            else if (rand() % 4 == 0)
                graph[i][j] = INF;  // No edge
            else
                graph[i][j] = rand() % 20 + 1;
        }
    }

    seq_dist = graph;
    par_dist = graph;

    // ---------------------------
    // 1. Sequential Floyd–Warshall
    // ---------------------------

    double start_seq = omp_get_wtime();

    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (seq_dist[i][k] < INF && seq_dist[k][j] < INF) {
                    seq_dist[i][j] = min(seq_dist[i][j],
                                          seq_dist[i][k] + seq_dist[k][j]);
                }
            }
        }
    }

    double end_seq = omp_get_wtime();
    double seq_time = end_seq - start_seq;

    // ---------------------------
    // 2. Parallel Floyd–Warshall
    // ---------------------------

    double start_par = omp_get_wtime();

    for (int k = 0; k < V; k++) {

        // Parallelize only i and j loops
        #pragma omp parallel for collapse(2)
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (par_dist[i][k] < INF && par_dist[k][j] < INF) {
                    int through_k = par_dist[i][k] + par_dist[k][j];
                    if (through_k < par_dist[i][j]) {
                        par_dist[i][j] = through_k;
                    }
                }
            }
        }
        // Implicit barrier here before next k
    }

    double end_par = omp_get_wtime();
    double par_time = end_par - start_par;

    // ---------------------------
    // Verification
    // ---------------------------

    bool correct = true;
    for (int i = 0; i < V && correct; i++) {
        for (int j = 0; j < V; j++) {
            if (seq_dist[i][j] != par_dist[i][j]) {
                correct = false;
                break;
            }
        }
    }

    // ---------------------------
    // Print Results
    // ---------------------------

    cout << "All-Pairs Shortest Path (V = " << V << ")\n\n";

    cout << "Sequential Time: " << seq_time << " sec\n";
    cout << "Parallel Time:   " << par_time << " sec\n";

    cout << "\nSpeedup = " << (seq_time / par_time) << "x\n";

    if (correct) {
        cout << "\nResults match. Parallel APSP is correct.\n";
    } else {
        cout << "\nMismatch detected! Something is wrong.\n";
    }

    return 0;
}

/*
Output Example:
All-Pairs Shortest Path (V = 2000)

Sequential Time: 9.857 sec
Parallel Time:   5.522 sec

Speedup = 1.78504x

Results match. Parallel APSP is correct.
## Performance depends on core count and memory bandwidth.
*/