Shortest Path Algorithms in Graphs
(Page 1 of 4 )
I need more time. I do not have time for this. These are probably the two sentences that we use the most these days. It has often been observed that time is money -- and accomplishing a task in fewer steps can save time (and thus money). With graphs, this can be expressed as finding the shortest path, and has a number of practical applications. This eighth part of a 13-part article series on graphs takes a close look at ways to solve this common problem.
The following practical problem occurs. A new public person transport company arrives in town. They have a central bus station. They make a little survey in the town to determine which streets would have more clients. Now, given this favorable rate information about each street, we need to build the optimal routes, so we make the most cash with the least investment.
Another chapter in my series about graphs starts here. In this and the next part, the central problem concerning us will be to determine the minimal road between vertexes inside graphs (therefore for everything that may be represented by graphs). Today we are going to examine two methods, leaving two more for a future article.
Today we you will learn about Dijkstra’s Algorithm and the minimal road calculation based on topological order. Next time we will determine the same thing using the Bellman-Ford technique and the Roy-Floyd algorithm. Nevertheless, so you can understand what we will be discussing today, you should start with some basic knowledge that I already covered in my earlier articles.
First, you need to know the definition of graphs and trees, and how we can represent them in our programs (read An Insight into Graphs). Second, you should be familiar with the concepts like the fundamental circle system and the topological sort. For this you may want to read my articles entitled Circles and Connectivity in Graphs and Depth-First Search in Graphs.
When you have a general grasp of these concepts, you may read on. For solving the problem, we will use an array of n items where index v will show us the distance between the points from where we search for the minimal road to the others. In the future, we will refer to this as the root vertex (you will see why later).
Therefore, if the v is our root vertex, at index v in our array, it will be zero, as we already are in that point and no longer need to make any future steps; the distance is zero accordingly. If there exists no road between the root vertex and index, v the distance is infinity. In our programming world, we will settle for an INT_MAX divided by two (so we can add these up).
By definition, if there is a circle whose overall weight is negative, the distance of the points related to the circle is minus infinity. This is obvious, as we can always make a shorter path by just making another lap around the circle, eventually finishing up at minus infinity. The approach used by all of the algorithms I am going to show to you is the gradual approximation.
Next: The gradual approximation >>
More Code Examples Articles
More By Gabor Bernat
