From Wikipedia:

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.

The results of the experiment, as well as a thorough analysis of the implementation, can be found in the project.pdf file.

Just run the project.sbatch file, which will compile and execute all models on all graphs:

sbatch project.sbatch

• OpenMP

./omp-bf [threads] [graph_file] [-b BIDIRECTIONAL] [-d DEBUG]

• CUDA

./cuda-bf [graph_file] [mode] [-b BIDIRECTIONAL] [-d DEBUG]

The parameter mode can be set to 0 to run the program on a single-thread, otherwise it is run in parallel.

On both Linux and Windows, use the following commands to compile the project:

• OpenMP

gcc -o omp-bf openmp/omp_bellmanford.c -fopenmp -Wall

• CUDA

nvcc -o cuda-bf cuda/cuda_bellmanford.cu

Graph Maker:

python tools/graph_maker.py [-h] [-v NODES] [-e EDGES] [-neg | --negative | --no-negative]

Plotter:

python tools/plotting/plotter.py

In order to function, the plotter needs the files omp.csv and cuda.csv (generated by the programs) to be put in a results in the root of the project.