Dijkstra algorithm was designed by Dutch computer scientist Edsger W. Dijkstra in 1959. It is one of the most popular shortest path algorithms. This algorithm find shortest path to each node from a selected source node. It is a greedy aproach the visits all the nodes of graph simultaneously updating shortest path to all the nodes from one source node.
In Dijkstra initially all nodes are presumed to be on an infinite distance from the source and distance of source itself is considered 0. After that a simple traversal is done throught the graph, visiting all the nodes connected to current node and performing all possible relaxations in the process. Without any optimization and direct implementation this algorithm has a time complexity of O(n2 + m) where n is number of vertices in graph and m is number of edges, however this complexity can be improved upto O(nlogn + m) by using priority queue. Priority queue prioritizes the outgoing edges with maximum scope for relaxation in path size hence improving the runtime of algorithm.
Dijkstra algorithm however is not the all perfect algorithm for path finding as it is not functionable with a graph containing negative weight cycle and is prone to error when applied with such a graph. It is because in presence of negative weight cycle the chain of relaxations will never stop and lead to infinite loop. Hence, for dealing with graphs containing negative wewigt cycles Bellman-Ford and Floyd-Warshall allgorithms are used.
Further reading about Dijkstra:
CP-Algorithms - Dijkstra
Wikepedia - Dijkstra
Brilliant.org - Dijkstra
This algorithm bears the name of two American scientists: Richard Bellman and Lester Ford. Ford invented this algorithm in 1956 during the study of another mathematical problem, which was reduced to subproblem of finding shortest path in graph. Bellman in 1958 published an article devoted specifically to the problem of finding the shortest path, and in this article he gave the present form of this algorithm.
Like Dijkstra this algorithm also finds shortest paths to all nodes from a selected source nodes. This algortihm also assumes initial distance to all the nodes to be infinity and distance to source 0. However unlike Dijkstra which updates the node based on there distances and connection to the current node this algorithm iterates through all the edges n - 1 times doing possible relaxation in each iteration. Here n is number of nodes in the graph. Each iteration runs for m times where m is number for edges in the graph. Hence, time complexity of Bellman-Ford after maximum optimization also is O(n * m) which is slower than optimized Dijkstra. However Bellman-Ford algorithm is capable of identifying negative weight cycle in a graph. This algorithm assumes that no further relaxation in path weight should be possible after n - 1 iterations and this can be proven mathematically until unless there is a negative weight cycle present in graph. Therefore completing n - 1 iterations one more iteration is done and if even a single relaxation is done during this iteration it is found that the graph contains a negative weight cycle.
Further reading about Bellman-Ford:
CP-Algorithms - Bellman-Ford
Wikepedia - Bellman-Ford
Brilliant.org - Bellman-Ford
This algorithm was been simultaneously published in articles by Robert Floyd and Stephen Warshall in 1962. However, in 1959, Bernard Roy published essentially the same algorithm, but its publication went unnoticed.
Unlike Dijkstra and Bellman-Ford this algorithm finds shortest path between all pair of edges i and j for a given graph. This algorithm can also be used to determine negative weight cycle in which case the shortest path doesn't exist. Unlike previous two algorithms this algorithm isn't a greedy approach and is actually a Dynamic Programming solution hence a basic intution of Dynamic Programming is necessary for understanding this algorithm. The Floyd–Warshall algorithm compares all possible paths through the graph between each pair of vertices. It is able to do this with Θ(|V|3) comparisons in a graph, even though there may be up to Ω(|V|2) edges in the graph, and every combination of edges is tested. This leads to the worst case complexity of O(|V|3).It does so by incrementally improving an estimate on the shortest path between two vertices, until the estimate is optimal.
Consider a graph G with vertices V numbered 1 through N. Further consider a function shortestPath(i, j, k) that returns the shortest possible path from i to j using vertices only from the set {1, 2, .. k - 1} as intermediate points along the way. If we include node k also in our list there are two possibilities : i) The older path that didn't include k is smaller, or ii) Including k leads to a shorter path, therefore path that includes k can be divided into two parts, shortestPath(i, k, k - 1) and shortestPath(k, j, k - 1). This computation can be done recursively using dynamic programming. This algorithm can be also used to determine negative weight cycles in graph.
Further reading about Floyd-Warshall:
CP-Algorithms - Floyd-Warshall
Wikepedia - Floyd-Warshall
Brilliant.org - Floyd-Warshall