Skip to content

README.md

Latest commit

 

History

History
78 lines (55 loc) · 2.93 KB

README.md

File metadata and controls

78 lines (55 loc) · 2.93 KB

Shortest Paths Algorithms

Dijkstra Algorithm

This algorithm finds shortest paths from the source to all other nodes in the graph, producing a shortest path tree. Its time complexity is $O(V + E; log; V)$ but can reach less than that when using priority queue. Dijkstra algorithm can’t handle negative weights. But, it is asymptotically the fastest known single-source shortest path algorithm for arbitrary directed graphs with unbounded non-negative weights.

Time Complexity : $O(V + E; log; V)$

Space Complexity : $O(V)$

Bellman-Ford Algorithm

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 directed graph. It is capable of handling graphs in which some of the edge weights are negative numbers. It works in O(V ∗ E) time and O(V ) space complexities where V is the number of vertices and E is the number of edges in the graph. It can detect the presence of a negative cycle in the graph.

Time Complexity : $O(V ∗ E)$

Space Complexity : $O(V)$

Floyd-Warshall Algorithm

The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths of shortest paths between all pairs of vertices. It works in O(V^3) time complexity. It can detect the presence of a negative cycle in the graph.

Time Complexity : $O$( $V^3$ )

Space Complexity : $O$( $V^2$ )

Comparison between Algorithms

Mean Time to get the shortest path between 2 specific nodes (ms)

Graph Size Graph Density Dijkstra Bellman-Ford Floyd-Warshall
10 Sparse 0.01 0.03 0.04
10 Dense 0.02 0.04 0.05
30 Sparse 0.00 0.03 0.19
30 Dense 0.11 0.10 0.43
50 Sparse 0.00 0.05 0.25
50 Dense 0.13 0.46 0.42
100 Sparse 0.00 0.15 0.81
100 Dense 0.56 3.17 1.99
500 Sparse 0.01 3.98 78.45
500 Dense 10.36 978.67 164.09
1000 Sparse 0.02 15.59 594.52
1000 Dense 57.80 14186.08 1216.22

Mean Time to get the shortest path between all pairs of nodes (ms)

Graph Size Graph Density Dijkstra Bellman-Ford Floyd-Warshall
10 Sparse 0.12 0.32 0.04
10 Dense 0.23 0.36 0.05
30 Sparse 0.04 0.70 0.20
30 Dense 2.89 2.54 0.43
50 Sparse 0.05 2.01 0.26
50 Dense 6.97 19.88 0.44
100 Sparse 0.07 13.24 0.88
100 Dense 56.58 314.67 2.08
500 Sparse 1.37 1881.79 80.91
500 Dense 7203.32 661665.36 162.42
1000 Sparse 3.02 16333.73 599.27
1000 Dense 75831.92 4623312.27 1187.51

Contributors

  • AbdElRahman Bassam

  • AbdElRahman Osama

  • Ahmed Youssef

  • Mohamed Mahfouz

  • Mourad Mahgoub