Question

Please help me with this answer.

Performance Comparison for Dijkstra Algorithm and Bellman-Ford Algorithm

Problem Description

The shortest path problem is one of most important problems in graph theory and computer science in general. Shortest path problem is one of typical optimization problems. Given a graph G = (V,E), the goal is to nd a minimum cost path from s → t, s,t ∈ V . This variant is called one-to-one shortest path problem. Other variants are one-to-all (compute shortest path from vertex s to every other vertex t ∈ V ), and all-to-all (compute shortest path between every possible pair (s,t) ∈ V ×V ). Certain graph attributes, such as edge direction or weight (cost) function, may aect algorithm performance and usability.

Dijkstra algorithm, Bellman-Ford algorithm, Floyd-Warshall algorithm, and A* algorithm are some of the most famous and most important algorithms to solve the shortest path problem. Performance of A* is determined by the heuristic you use, and in general performs very well in the basic one-to-one variant. Floyd-Warshall algorithm is used to solve all-to-all shortest path problem, but is easily outperformed in one-to-all and one-to-one variants. Because these algorithms have dierent objective, it is hard to make a fair comparison of their performance. However, we can compare Dijkstra algorithm and Bellman-Ford algorithm in one-to-all problem. In algorithm class, we have learned Dijkstra algorithm and Bellman-Ford algorithm to solve one-to-all shortest path problem.

These two algorithms use dierent approach and have dierent time and space complexity, depending on implementation details and level of optimization eort. Performance of Djikstra algorithm is determined by data structure used to nd minimum distance vertex. We can use min-heap (Binary or Fibonacci heap) to store and update candidate vertices eciently (call this version D). Performance of Bellman-Ford algorithm can be aected by stopping the iterations when possible. We can stop iteration　of vertices which are reached by starting vertex and not be updated (call this version B). Also, note that algorithm performance can be aected by data structures used to store vertices (adjacency matrix or adjacency list).

Please implement D and B and compare their performance. You should test both using dierent, large enough test cases; you might get incorrect results on a small test case. Remember that algorithm complexity may require a large input to express its properties.

One of the requirements of this assignment is to test the algorithms on various test cases. Note that it is not a simple task to create such test cases; your generator will probably have some bias that will be common for all the graphs generated. Therefore, you might consider using more than one generator to provide various examples. Remember to describe and justify your choice in the attached documents.

Technical Specication

In your report, you have to include source code for each program you have used. In a typical case, there will be at least 3 programs, namely Dijkstra algorithm, Bellman-Ford algorithm, and test-case generator. Also, you should describe what test cases you used, the way you obtained them and method used to measure algorithm's performance. Finally, include a conclusion describing expected correlation between theoretical knowledge and practical results.