Shortest paths: Dijkstra and Floyd 2
Dijkstra algorithm
Dijkstra Algorithm provides a possibility to solve that sort of problem to find the optimal (that means the shortest) path from the fixed start node to the target node. The nodes are the labels for the points that have to be achieved. And the edges represent the distances between the nodes.
For example if you want to go from Kaiserslautern to Mannheim and your path would be quantify in kilometer, your shortest path is down the highway through Bad Dürkheim and Hochspeyer but not direct down the freeway.
Primarily you should select starting node as a base node. Compute the distance from starting node to all neighbor nodes. That one is the new base node which has the shortest path to starting node. Compute the distance from new base node to all neighbor nodes of the base node which have not been base node yet.(???) Continue until you achieve the target node.
Example
The following example shows how it is possible to find the shortest path from node 1 to node 3. The nodes represent the cities in a graph and the edges are the distances between the cities.
Mission: calculation of the shortest way from 1 to 3.
- At first you have to define your starting node and fix it as a base node.
- Start to detect the distances from this point to all his neighbors.
- After that identify the shortest distance between these nodes.
- Choose the node as the next base node which has the shortest connection to the first base node.
- If it not the node you want to achieve (If the base node is not the one you want to achieve you have to continue [...]), continue with the identification of the next base node, which has the shortest distance to the predecessor base node.
The first base node here is 1. Now you can notice which neighbors has this node. Also you can notice the distances:
The shortest distance is between the node 1 and node 5. Therefore, your next base node will be node 5. You have to identify the neighbors of the new base node and the distances between:
Now you can see - the shortest way to achieve the node 2 is from 1 to 2 with the distance 4. Therefore you do not observe the way 1-5-2 anymore, because it is longer.
Now you choose the next base node. There must be the nodes, which have not been base node yet. You can choose between 2, 3 and 4. It is important for your decision to search for a shortest distance. Now it is node 2. You search for the neighbors again and notice the distances:
There are two possibilities to achieve the node 3 here. You choose the shortest: 1-5-3.
The same applies for a node 4. The shortest path from 1 to 4 is 4.
The next best base node from all residual possible nodes is 4, because the distance 4 is smaller than 8. The neighbors and distances are entered in the table:
If we compare the distances to node 3, it is obvious, that the distance from node 1 to 3 through the nodes 5 and 4 is shorter. So you have the table with the results:
Conclusion: the shortest path from node 1 to 3 is possible with the distance 6 through the nodes 5 and 4: 1-5-4-3.
Floyd algorithm
In the graph theory we have beside the Dijskra algorithm another algorithm to find the shortest way between two nodes: The Floyd algorithm. This algorithm, grounded by Robert Floyd, has one special compared to Dijkstra. You will find not only the shortest path from one start node to the other nodes, but the shortest paths from all nodes to all other nodes and their corresponding lengths.
The idea of the Floyd algorithm is to compare the length of the path from node i to node j via the detour node 1. If this path is shorter, the direct way will be deleted. After that, all connections will be compared via the detour node 2 and so on.
You can use this algorithm e.g. if there is a company with a lot of branches. And all branches must be supply with articles. So, you can calculate in every situation the shortest path to the next branch.
Example
Here we compare all possible paths through the graph between each pair. We have to test and notice all combinations of edges.
- At first we have to notice in the table all distances and predecessors of all possible directly connections. If it exists no directly connection between the nodes, the distance is infinitely.
- After that you have to search for the possible indirectly connections with better value of distance for each node.
- After the testing of all possibilities the finish table will provide you with the information about the best distances.
Let us see it on an example.
The distances should to be noticed in the table.
Now we want to see, if it exists indirectly connection from all nodes to each other and if the distance of the detour is shorter as a directly connection, choose this.
At first we search for the possibilities to improve the ways through the node 1:
We compare the distances of all directly connections (not marked fields) and detours through the node 1.
From 2 to 3 the directly distance is 10 and the predecessor is the node 2.
If our detour node is node 1, we can identify the other possible way: from 2 to 1 and from 1 to 3. The new length is (4 + ∞). This is not better as directly connection. Therefore - no improvement.
If you find the shorter distances you have to notice this in the table.
Compare all possible connections with all detour notes:
Now you can see, we have improved the distances.
Our mission was to find the shortest path from 1 to 3: from 1 to 4 and from 4 to 3. The distance is 6.
Sources
D. Jungnickel, "Graphen, Netzwerke und Algorithmen", BI Wissenschafts-Verlag (1994)
H. Müller-Merbach, "Operations Research", 3.Auflage, Verlag Franz Vahlen (1973)
https://bisor.wiki.uni-kl.de/orwiki/Dijkstra_Algorithmus
https://bisor.wiki.uni-kl.de/orwiki/Floyd_Algorithmus
Authors: Arina Furasev, Ludmilla Rechtik, Christoph Ruffing
