In this article, I describe the Bellman-Ford algorithm for finding the one-source shortest paths in a graph, give an informal proof and provide the source code in C for a simple implementation.
To understand this you should know what a graph is, and how to store one in memory. If in doubt check this and this.
Another solution to this problem is Dijkstra’s algorithm.
The Problem
Given the following graph, calculate the length of the shortest path from node 1 to node 2.
It’s obvious that there’s a direct route of length 6, but take a look at path: 1 -> 4 -> 3 -> 2. The length of the path is 7 – 3 – 2 = 2, which is less than 6. BTW, you don’t need negative edge weights to get such a situation, but they do clarify the problem.
This also suggests a property of shortest path algorithms: to find the shortest path form x to y, you need to know, beforehand, the shortest paths to y‘s neighbours. For this, you need to know the paths to y‘s neighbours’ neighbours… In the end, you must calculate the shortest path to the connected component of the graph in which x and y are found.
That said, you usually calculate the shortest path to all nodes and then pick the ones you’re intrested in.
Read full article from One Source Shortest Path: The Bellman-Ford Algorithm | Computer programming
No comments:
Post a Comment