In this project, serial and parallel version of bellman ford algorithm for single source shortest path is implemented
This repository contains implementations of the Bellman-Ford algorithm for Single Source Shortest Path (SSSP) problem in three different ways:
bellman-ford-sssp-serial.cpp
)bellman-ford-sssp-pthread.cpp
)bellman-ford-sssp-simd.cpp
)The program automatically downloads and uses the higgs-twitter.mtx
data file for its operations. This dataset is part of the Higgs Twitter dataset, which captures the spread of news about the discovery of a new particle with the features of the Higgs boson on 4th July 2012.
The code can be compiled and executed using the g++
compiler for the serial and parallel implementations. However, for the SIMD vectorized version, the ARM architecture
is needed.
Please follow the instructions below to compile and execute the programs:
g++ bellman-ford-sssp-serial.cpp graph.cpp dataset_operations.cpp -o bellman-ford-sssp-serial -std=c++20 -lcurl
./bellman-ford-sssp-serial
g++ bellman-ford-sssp-pthread.cpp graph.cpp dataset_operations.cpp -o bellman-ford-sssp-pthread -std=c++20 -lpthread -lcurl
./bellman-ford-sssp-pthread
The SIMD vectorized version of the program is designed to run on ARM architecture, specifically using ARM NEON intrinsics for SIMD vectorization.
g++ bellman-ford-sssp-simd.cpp dataset_operations.cpp -o bellman-ford-sssp-simd -march=armv8-a -mfpu=neon -std=c++20 -lcurl
./bellman-ford-sssp-simd