DESIGN THE PARALLEL PROGRAM FOR ALL PAIRS SHORTEST PATH
PROBLEM USING MPI LIBRARY
Aim :
To Design the parallel program for all pair shortest path problem using MPI library.
Procedure:
Step 1: Set Up Your Development Environment
1. Install MPI: Ensure you have an MPI implementation installed (like OpenMPI or
MPICH).
2. Choose a Programming Language: Use C or C++ for this implementation as MPI is
commonly used in these languages.
Step 2: Initialize MPI
1. Include MPI Header: At the beginning of your program, include the MPI header.
2. Initialize MPI: In your main function, call MPI_Init.
3. Get Rank and Size:
Step 3: Initialize the Graph
1. Define the Graph: Create a global variable to hold your graph.
#define MAX_VERTICES 100
int graph[MAX_VERTICES][MAX_VERTICES];
int dist[MAX_VERTICES][MAX_VERTICES]; // To hold shortest paths
2. Create Initialization Function:
o Write a function to initialize your graph with edge weights. Ensure you set
distances to INF for non-edges and 0 for self-loops.
Step 4: Implement the Floyd-Warshall Algorithm
1. Create a Function: Write a function that implements the Floyd-Warshall algorithm in
parallel.
2. Broadcasting: Use MPI_Bcast to share the current distance values across all
processes at each iteration.
3. Compute Distances:
o Each process will compute shortest paths for a portion of the vertices based
on its rank.
o Update the dist array with the new shortest paths using the current vertex
kkk.
4. Gather Results: After computation, gather all results back to the root process using
MPI_Gather.
Step 5: Finalize MPI
1. Print Results: On the root process, print or save the final shortest paths matrix.
2. Finalize MPI: Call MPI_Finalize at the end of your main function.
Step 6: Compile and Run