Parallel Path Planning Algorithms

This repository provides serial and parallel implementations of three classical shortest path algorithms — Dijkstra, Bellman-Ford, and Floyd-Warshall — using OpenMP (CPU parallelism) and CUDA (GPU acceleration). The algorithms are tested on both real-world and synthetic graph data to evaluate performance scalability.

---

Project Structure

planmux/
├── assets/                         # Algorithm-specific result assets (plots, charts)
│   ├── bellman_ford/
│   ├── dijkstra/
│   └── floyd_warshall/
├── config/                         # Runtime configuration files
│   └── default.yaml
├── results/                        # Benchmarking outputs
│   ├── jobs/                       # SLURM or local job output logs
│   ├── results.pdf                 # Consolidated result visualizations
│   └── results.xlsx                # Raw performance data
├── src/                            # All source code and executables
│   ├── main.cpp                    # Entry point for general testing
│   ├── USA-road-d_NY.txt           # Real-world graph dataset
│   ├── bellman_ford/
│   │   ├── bellman_ford_cuda.cu
│   │   └── bellman_ford_openmp.cpp
│   ├── dijkstra/
│   │   ├── dijkstra_openmp.cpp
│   │   └── dijkstra_openmp.sh
│   └── floyd_warshall/
│       ├── floyd_warshall_cuda.cu
│       ├── floyd_warshall_cuda.sh
│       ├── floyd_warshall_openmp.cpp
│       └── floyd_warshall_openmp.sh
├── .gitignore                      # Git ignored files and folders
├── LICENSE                         # Project license (MIT)
├── presentation.pdf                # Presentation (PDF version)
├── presentation.pptx               # Presentation (PPTX version)
├── report.pdf                      # Final technical report
└── README.md                       # Project documentation (you are here)

---

Algorithms Implemented

Algorithm	Serial	OpenMP	CUDA
Dijkstra	✅	✅	❌
Bellman-Ford	✅	✅	✅
Floyd-Warshall	✅	✅	✅

---

Build & Run

Prerequisites

• C++ Compiler: g++ with OpenMP support (-fopenmp)
• GPU Support: NVIDIA GPU + CUDA Toolkit (nvcc)
• Shell Environment: Bash (Linux, WSL, or Git Bash on Windows)
• If on Windows, ensure Visual Studio Build Tools are installed and properly configured
• For CUDA builds on Windows, you must provide the correct path to cl.exe via -ccbin

Compilation Examples

Dijkstra (OpenMP)

g++ ./src/dijkstra/dijkstra_openmp.cpp -o dijkstra_openmp -fopenmp -std=c++17
./dijkstra_openmp <num_nodes> <num_threads>

Bellman-Ford (OpenMP)

g++ ./src/bellman_ford/bellman_ford_openmp.cpp -o bellman_ford_openmp -fopenmp -std=c++17
./bellman_ford_openmp <num_nodes> <num_threads>

Bellman-Ford (CUDA)

nvcc ./src/bellman_ford/bellman_ford_cuda.cu -o bellman_ford_cuda -ccbin "C:/Path/To/cl.exe/Folder"
./bellman_ford_cuda <num_nodes>

Floyd-Warshall (OpenMP)

g++ ./src/floyd_warshall/floyd_warshall_openmp.cpp -o floyd_warshall_openmp -fopenmp -std=c++17
./floyd_warshall_openmp <num_nodes> <num_threads>

Floyd-Warshall (CUDA)

nvcc ./src/floyd_warshall/floyd_warshall_cuda.cu -o floyd_warshall_cuda -ccbin "C:/Path/To/cl.exe/Folder"
./floyd_warshall_cuda <num_nodes>

---

Dataset Information

• USA-road-d_NY.txt: New York road network from the DIMACS Challenge Dataset
• Synthetic graphs: Randomly generated with controlled node/edge parameters (see assets/)

---

Results

Results are summarized in the following files:

• results/results.pdf: Performance graphs and discussion
• results/results.xlsx: Raw benchmarking data (execution time, speed-up, etc.)

Performance was evaluated on:

• Execution time (serial vs. OpenMP vs. CUDA)
• Varying graph sizes (sparse to dense)
• Real vs. synthetic graphs

---

Documentation

• report.pdf: Complete technical report with algorithm details and experimental results
• presentation.pptx: Final presentation slides

---

Authors

• Aaron John Sabu – @aaronjohnsabu1999
• Athul CD – @athulcd
• Ayan Sharma – @ayan-2004
• Vaibhav Malviya – @Vaibhav110

---

License

This project is licensed under the MIT License. See the LICENSE file for details.