EXPERIMENTAL EVALUATION OF SHORTEST PATH ALGORITHMS - DIJKSTRA VS BELLMAN FORD

Background: Shortest path algorithms play an important role in any path finding the application. These algorithms have been in existence since the mid-1960's. Year after year many of improvements in existing algorithms have led to new efficient algorithms.This work compares two common shortest path algorithms which have played an important role in a complex map based and network based applications viz. Dijkstra and Bellman-Ford. These algorithms were discovered a long time back and still we are using them as an optimum solution for finding the shortest path. In this research work, statistical data showing how these two algorithms behave differently when we conduct experiments with different parameters will be presented. For these experiments 1 GB of data viz. A number of nodes and edges will be varied and passed to these two algorithms and clock cycles per instruction performance of the processor will be measured in terms of nanoseconds. We expect experiments to create a new direction in choosing one of these to provide the best results depending on situations. Finding the shortest distance is a tedious job. It gets worse when there are millions of paths that exists and choosing the best path with the shortest distance in minimum time duration. Applications require a huge amount of calculations to find the shortest path in terms of CPU and memory intensive operations which are not only time consuming but also requires a lot of memory and CPU. This limits other processes waiting to access CPU and memory. Generating statistical results of such memory intensive operations will give a clear idea regarding what algorithms worked best in certain conditions and what algorithm was worst in certain conditions. This data can give clear idea that anyone could easily judge whether to choose Dijkstra or Bellman-Ford. This will certainly help researchers and programming enthusiast to better choose the best algorithm which leads their application run more efficiently. Methods and Results: These experiments will be implemented in C++11 programming language and POSIX Linux platform. A data file containing nodes and edges will be passed from the command line to each of the implemented algorithms. This will ensure unnecessary cycles per instruction will not be counted in results. Results generated from these experiments will provide a clear idea of in what extend Dijkstra and Bellman-Ford are improved and which of these two works best in what conditions. Statistical analysis will be presented on this poster is based on results of these experiments. Conclusion: Ultimate goal of this experimentation is improving runtime complexity of Dijkstra and Bellman-Ford. With these research experiments, we expect to generate statistical results which will be a starting point to find out an improvised version of Dijkstra and Bellman-Ford.