Though Dijkstra's algorithm is the most popular and efficient one that is used to find the single source shortest path, there is one problem that it does not address. If the graph has a negative cycle, Dijkstra's algorithm cannot detect the negative cycle, and, thus, it does not work. A negative cycle is a cycle where the sum of all the edges in the cycle is negative. If a graph contains a negative cycle, then finding the shortest path will not be possible, so it is important that we address the issue while finding the shortest path. That is why we use the Bellman-Ford algorithm, even though it is slower compared to Dijkstra's algorithm. Here is the algorithm pseudocode for the Bellman-Ford ...
Finding the shortest path using the Bellman-Ford algorithm
Get PHP 7 Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
