Complexity Differences Between the Shortest Path Algorithms
Here V and E, denote the number of vertices and the number of Edges in the graph respectively.
|
Algorithm |
Time Complexity |
Space Complexity |
|---|---|---|
|
O(V + E) |
O(V) |
|
|
O(V+E) |
O(V) |
|
|
O(V+E) |
O(V) |
|
|
O(E*log(V)) |
O(V) |
|
|
O(V*E) |
O(V) |
|
|
O(V^3) |
O(V^2) |
|
|
O(E*log(V)) |
O(V) |
|
|
O(V^2 * log V + V*E) |
O(V^2) |
Comparison between Shortest Path Algorithms:
Finding the shortest way is becoming more important in a world where time and distance matter. There are multiple shorted path algorithms exists. Therefore, in this article, we will compare the shortest path algorithms on the basis of their complexity and their performance, which will help us to use the correct algorithm according to our requirements.
The shortest path algorithms are the ones that focuses on calculating the minimum travelling cost from source node to destination node of a graph in optimal time and space complexities.
In this article we’re focusing on the differences between shortest path algorithms that are: