Shortest paths: Dijkstra and Floyd 1

1. Dijkstra Algorithm

1.1. Theory

The Dijkstra-algorithm was formulated by Edsger Wybe Dijkstra. He was a dutch computer scientist and very popular for his papers in programming. Dijkstra was born in 1930 in Rotterdam and died in 2002 in Nuenen, The Netherlands. In 1972 he became famous while winning the Turing-Award. It is one of the most popular prizes you can get in informatics and it’s comparable to the Nobel Prize.

This algorithm is used for the calculation of the shortest path between the starting-point and the final-node. There are different ways to get a solution. But in this concept, the goal is to find the optimal solution for the given problem. Although the aspects of the shortest path and the cheapest way are essential for the Dijkstra-algorithm.

The idea of this algorithm is to compare the starting point with each proximate node of the graph. The reflection of the base node is also very important in this pattern.

1.2. Example

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

To resume, the steps to solve a problem with the tool of Dijkstra algorithm are:

-->You have to choose a base node

-->You should calculate the distances between the base node and the nodes nearby. After this calculation you should compare the results and formulate new base nodes. The new basis is that point where the distances, which you get from the calculation, are the smallest.

-->After the whole calculation, the result should be, base node is equal to the final node.

1.3. Description of the given example

Given are the starting node A and the final node F. Now the task is to find the shortest path from A to F. The first thing to do is to mark node A as the first base node (perhaps by colouring it). As one can see A has two nodes as neighbours which haven’t been base nodes yet, namely node B and node C. the distance from A to B is 7, while the distance from A to C is 8. Choose the one node that is the nearest to A, which is node B. Now you mark B as the second base node. B’s not yet visited neighbours are C and D. The distance from starting node A to D via B is 12 (7+5) and the distance from A to C via B would be 9 (7+2). We can now see that there’s a shorter way to get from A to C, the shorter way is the direct one with distance 8. Because C has now the shortest distance to A, we choose C as the new base node and kick out the old path which was A-B-C. Standing at node C we recognize D and E as the new direct neighbours which haven’t been visited yet. The distance from A to D via C adds up to 13 (8+5), but we already know a shorter path, namely the one from A to D via B which is 12. It’s time to check the other direct neighbour of C, node E. The shortest way to get from A to E goes via C with the distance of 15. We now select the shortest calculated distance so far, to find the new base node. Our decision is node D we reach it via B. D has only one direct neighbour which hasn’t been base node yet, namely node F. The shortest way to F is A-B-D-F with a length of 18 (7+5+6). We now choose F as the new base node and since F is our final node to reach the algorithm ends here and we know that the shortest way from our starting node A to our final node F has the distance of 18 and goes via B and D.

2. Floyd Algorithm

2.1 Fundamentals

In graph theory there are two fundamental issues in the calculation of shortest paths. This object is achieved with the Dijkstra algorithm (described in chapter 1). The second case investigates the shortest paths from each node to all other nodes. This could be solved with a list of all possible trees and the calculation using also the Dijkstra algorithm. However, this would be very expensive. Such a problem can much easier be solved by using the Floyd algorithm.

Named after Robert Floyd, the algorithm is very easy to calculate and can be programmed easily as well. Mr. Floyd was an computer scientist. His contributions include the design of the Floyd–Warshall algorithm, which efficiently finds all shortest paths in a graph, Floyd's cycle-finding algorithm for detecting cycles in a sequence. A significant achievement was pioneering the field of program verification using logical assertions with the 1967 paper Assigning Meanings to Programs. This was an important contribution to what later became Hoare logic.

The basic idea in the Floyd algorithm is, to compare the length of the path of a node i to node j over the nodes with the detour via node 1 at first first. When the "detour" via node 1 is shorter than the direct path, the old one is discarded. Once all of the way through the detour node 1 are compared, we compare all paths through the detour node 2. And so on...

2.2 Example

The task is to determine the shortest paths between all pairs of nodes on transportation network which are placed in the graph below. A length of a branch is shown with a number at a line.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Before starting one needs a starting matrix D0. Furthermore this tells one how long the distances to other nodes are.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

2.2 Description of the 2nd Example

Given the starting matrix the first step to do, is to is to cross out column 1 and row 1 and the zeros on the diagonal (because a shortest path from a node to himself doesn’t actually exist). So node 1 is chosen to be our first detour node.

The task now is to check every distance from every node to every other given node, except for the crossed out distances. The first path we can look at is the one from node 2 to node 3. Our starting matrix shows us, that the shortest distance is 2, namely the direct route. Now we need to check if there’s any possibility that the path can be shortened by going via detour node 1 first. If we go from node 2 to node 1 (detour node) and then to node 3, the distance adds up to 11 (8+3). So it’s not shorter to go from 2 to 3 via 1 → we kick this possibility out and leave the shorter distance, which is 2 at the moment, in our matrix.

The next path we can check, is the one from node 2 to node 4. Right now it has an infinite distance, because there is no direct connection between this nodes, but if we go via the detour node (which is still 1) we find out that the path has a distance of 13 (8+5) which is obviously shorter → the old path with the infinite distance gets kicked out and is replaced by the new shortest distance of 13.

Going on, we find out that there are shorter distances from node 4 to node 2 and from node 4 to node 3, via detour node 1. In the first case (from 4 to 2) our old shortest path is the infinite one, but we can see that it’s better to go via the detour node 1, because then the distance shortens to 14 (6+8). In the second case (from 4 to 3) the new shortest distance we detect is 9 (6+3), via detour node 1 as well.

The numbers below the shortest distances represent the direct predecessors, in the case of an infinite distance we write a minus symbol (-).

We have a new matrix now, with some new shortest distances and some old ones.

The next step would be to cross out column 2 and row 2 of this new matrix, which means that we chose node 2 to be our next detour node. The distances given in column 1 and row 1, that were crossed out before, need to be inspected again. Now the same procedure to check out all the distances, except for the new crossed out ones (the distances in row 2 and column 2) starts again.

At the end, each of the five given nodes should have been a detour node and all the shortest paths should have been found.

The final solution can be seen in the following matrix:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden