Lecture
This article is about a fairly intricate route-finding algorithm on graphs. Incidentally, graphs are not only harder to understand, they are also unusual to look at visually. But that's only true at first. Today we'll talk about Shimbel's algorithm.
Our main task will be to find the shortest path. But the path itself will be of a different kind here. This (see figure) is what a directed graph looks like.
Obviously, the routes here are more tangled, since the vertices have different distances between them. Incidentally, it isn't only distance that can differ — the cost of a trip can too. In general, the criterion for choosing a route can be anything at all. But a graph has to be built on the basis of it.
A matrix is built from the graph. This matrix shows the distances between the graph's accessible vertices. It is called the weight matrix.
From the direction arrows on the graph it is clear that we can get from the fourth vertex of the graph to the fifth, and back as well. But from the second vertex we can get to the fifth, while going back — not at all. The fields of the matrix are filled in accordingly. If there is no path, we write 0.
Weight matrix
|
0 |
1 |
2 |
3 |
4 |
5 |
|
1 |
0 |
10 |
0 |
0 |
0 |
|
2 |
0 |
0 |
12 |
0 |
8 |
|
3 |
0 |
0 |
0 |
8 |
0 |
|
4 |
0 |
6 |
8 |
0 |
3 |
|
5 |
0 |
0 |
0 |
3 |
0 |
One of the mathematical solutions to such problems is Shimbel's algorithm, based on a clever way of adding matrices. What's the trick? To find the shortest path between two vertices made up of two edges, we take, in turn, each element of the row and column corresponding to the numbers of the vertices and add them together. Any operation involving at least one zero is ignored. And out of the resulting sums we pick the smallest one. It's very easy to picture such a graph — imagine a network of roads with checkpoints, somewhere in Donbass or in Syria. Situations can easily arise where some checkpoints are closed, others are ordered to let refugees through in one direction only, and at still others the guards simply flee, leaving the way open. There you have a directed graph. The weight matrix will be the main tool we'll be working with.
So, the path from element 3 to element 2.
0+10 (0)
0+ 0 (0)
0 +0 (0)
8+6 (14)
0+0 (0)
The only operation that satisfies our conditions gives 14. Now look at the figure right at the top – the only shortest path of two edges from vertex 3 to vertex 2, via vertex 4, has a weight of 14. This is shown on the matrix of shortest paths of two edges, given below.
Matrix of shortest paths of two edges
|
0 |
1 |
2 |
3 |
4 |
5 |
|
1 |
0 |
0 |
22 |
0 |
18 |
|
2 |
0 |
0 |
0 |
11 |
0 |
|
3 |
0 |
14 |
0 |
0 |
11 |
|
4 |
0 |
0 |
18 |
0 |
14 |
|
5 |
0 |
9 |
11 |
0 |
0 |
The algorithm may seem somewhat complicated, but in fact it is very basic arithmetic. And programming it takes just a few lines, if you don't need to “draw” a visual interface. But… you will still need to think hard if you've forgotten the rules for working with two-dimensional matrices.
I decided not to make you strain yourselves and worked out an elementary solution. As a first approximation we need to go through every element of a two-dimensional array in a double loop. We also need a third loop, nested inside the first two, which will, at every step, add together the element of the row and column being sought.
Along with this we need to set up a simple set of conditions that will help us discard operations where at least one zero appears, and operations with matching row and column numbers (see the example: the element at address 3.4 can be computed, but 3.3 – that's vertex 3. And from vertex 3 we can't go to vertex 3, since we're already there).
When computing the matrix of paths of three edges, we will need to add together elements of the row and column of the first and second matrices obtained. Only the summands will change in the algorithm itself. There's no need to rewrite it.
|
0 |
1 |
2 |
3 |
4 |
5 |
|
1 |
0 |
0 |
0 |
21 |
0 |
|
2 |
0 |
17 |
19 |
0 |
23 |
|
3 |
0 |
0 |
26 |
0 |
22 |
|
4 |
0 |
12 |
14 |
17 |
19 |
|
5 |
0 |
0 |
21 |
0 |
17 |
Flowchart of the algorithm for finding shortest paths in a graph using Shimbel's method
Shimbel's algorithm is far from the most efficient way of finding shortest edges, in terms of memory usage and execution speed, but it is very useful for understanding how loops and conditions work. That's why professors at universities are so fond of assigning it.
So: here is a short snippet of Java code that finds the shortest paths made up of two and three edges of the graph. The code works, and can be used to build your own methods, classes, and to solve lab assignments.
Comments