Vocking B., Alt H., Dietzfelbinger M., Reischuk R., Scheideler C., Vollmer H., Wagner D. Algorithms Unplugged
Подождите немного. Документ загружается.
320 Peter Sanders and Johannes Singler
tion from the starting knot to v using only hanging knots. As long as there
are no “hanging connections,” d[v] is infinite. Therefore, in the beginning,
d[starting knot] = 0, and d[v] = infinite for all other knots.
The pseudocode given here describes the calculation of all knots’ distances
to the starting knot:
Dijkstra’s Algorithm in Thread Terminology
1 all knots are waiting, all d[v] are infinite, only d[starting knot]=0
2 while there are waiting knots do
3 v := the waiting knot with the smallest d[v]
4Turnv hanging
5 for all threads from v toaneighboru of the length do
6 if d[v]+<d[u], then d[u]:=d[v]+
// found shorter path to u, leads via v
How is this algorithm linked to the process of slowly lifting up the starting
knot? Each iteration of the while-loop corresponds to the transition of knot
v from waiting to hanging. The next knot lifted in turn is the waiting knot
v of the smallest value d[v]. This value is the height to which we have to lift
the starting knot to make v hanging. Since other threads lifted to this height
later on cannot decrease it, d[v] is the definitive distance from the starting
knot to v.
The plus side of Dijkstra’s algorithm is that the d[u] values of the other
knots can easily be adapted when v becomes hanging: only the threads starting
from v have to be considered, which is done by the inner for-loop. A thread
between v and a neighboring knot u of the length builds a connection of
the length d[u]:=d[v]+ from the starting knot to u. If this value is smaller
than the last value of d[u], the latter is diminished accordingly. In the end, all
knots reachable from the starting knot are hanging and the d[u]valuesgive
the lengths of the shortest paths.
In the following, you see some steps in the execution of the algorithm.
Hanging knots are orange, blue ones are waiting and the remaining, as of yet
unreached knots are white. Inside the circles the current d[u] is given. After
the algorithm has finished you can go backwards from the target knot and
along the red threads to find the shortest path.
The algorithm starts with the following configuration, when all knots are
still lying on the table.
32 Shortest Paths 321
The next figure shows the algorithm’s state after ten steps, i.e., the same
situation as in the hanging thread web in this chapter’s first figure.
322 Peter Sanders and Johannes Singler
The end state looks like this: All knots are hanging in the air, and the
shortest paths from M lead along the red threads.
With my computer implementation, I can now calculate distances between
knots to my heart’s content, without having to clean up ashes or disentan-
gle threads. My anger is subsiding slowly, and maybe my brother will not be
permanently banned from my flat after all. However, for real route planning,
I must expand Dijkstra’s algorithm to make the shortest paths themselves
available. Whenever d[u] is set to a new value, the program remembers which
knot was responsible for this: knot v that has just been lifted. In the end,
the route is reconstructed by going backwards, following the predecessor in-
formation from the target to the start knot. The pointers contain the same
information as the red threads in the figures.
FAQs and Further Reading
Where can I find a more detailed description of Dijkstra’s algo-
rithm? There are many good algorithm textbooks explaining everything there
is to know, e.g., K. Mehlhorn, P. Sanders. Algorithms and Data Structures –
The Basic Toolbox. Springer, 2008.
Who was Dijkstra? Edsger W. Dijkstra (http://de.wikipedia.org/wiki/
Edsger
Wybe Dijkstra) was born in 1930 and died in 2002. Not only did he
invent the algorithm described above, he also made substantial contributions
in the field of systematic programming and to the modelling of parallel pro-
cesses. In 1972 he was presented with the Turing Award, the most prestigious
32 Shortest Paths 323
award for computer scientists. His famous article “A note on two problems
in connexion with graphs” was published in 1959 in the journal Numerische
Mathematik. The “other” problem he mentions is the calculation of minimum
spanning trees. If you leave out the “d[v]+” in line 6 of our pseudocode you
get the Jarn´ık–Prim algorithm from Chap. 33.
What are threads, etc., in “technicalese”? Knots are called nodes in
computer science; instead of threads we have edges. Networks of nodes and
edges form graphs.
Have I not already come across something like this in this book?
In computer science, the search for paths and the related problem of finding
circles are very important.
• Depth search systematically lists certain paths, which is the basis of many
algorithms. See for example Chap. 7 (Depth-First Search) and Chap. 9
(Cycles in Graphs).
• The Eulerian Circles in Chap. 28 use each edge exactly once.
• The Travelling Salesman Problem described in Chap. 40 is concerned with
a round trip between cities that has to be as short as possible. Determining
the travelling time between the cities, however, is a shortest path problem.
How to implement the pseudocode efficiently? We need a data structure
that supports the following operations: insert nodes, delete nodes with the
shortest distance, and change distance. Since this combination of operations
is needed quite often, there is a name for it – priority queue. Fast priority
queues need time at most logarithmic in the number of nodes for any of the
operations.
Can we do this even faster? Do we really have to look at the whole
Western European road network in order to find the shortest path from Karl-
sruhe to Barcelona? Common sense says otherwise. Current commercial route
planners only look at highways when “far apart” from starting points and
destinations, but cannot guarantee not to overlook short cuts. In recent years,
however, faster procedures have been developed that guarantee optimal solu-
tions, see, for example, the work of our group http://algo2.iti.kit.edu/
routeplanning.php.
Is this a route planner for road networks only? The problem is much
more common than it seems. For instance, Dijkstra’s algorithm does not have
to know about a node’s geographical position, and is not limited to (spatial)
distances, but can also use travelling times as thread lengths. This even works
for one-way streets or differing travelling times for the trips from A to B
and back, since our algorithm only considers the thread length from start to
end. The network can also model many other things, e.g., public transport
including departure times, or communication channels in the internet. Even
problems that, at first sight, look unrelated to paths, can often be rephrased
appropriately. For example, the distance between two strings of characters
(genome sequences) in Chap. 31 can be interpreted as a distance in a graph.
324 Peter Sanders and Johannes Singler
Nodes are pairs of letters of the two inputs that are matched. Edges encode
the operations delete, insert, replace and transfer.
Is it possible to have streets of negative length? This can be quite
useful, e.g., it is possible to factor in that my favorite ice cream parlor is in
a certain street, so I do not mind detours. However, a round trip of negative
length is not allowed, otherwise you could go in circles for as long as you
like (eating ice cream) while the path is continuously becoming shorter –
the concept of the shortest path would not make sense anymore. But even if
there are no negative circles, Dijkstra’s algorithm could fail. The problem is
that via a knot already hanging, a thread of negative length could provide
improved routes for other nodes. Dijkstra’s algorithm does not handle this
case. A better-suited alternative is Bellman and Ford’s algorithm, which takes
more care to cover all cases but is much slower.
33
Minimum Spanning Trees
(Sometimes Greed Pays Off . . . )
Katharina Skutella and Martin Skutella
Technische Universit¨at Berlin, Berlin, Germany
Once upon a time in a remote island kingdom there lived the Algo clan.
The clansmen lived scattered all over the seven islands of the kingdom shown
below.
The seven islands and the mainland were connected by several ferries al-
lowing visits and excursions to the mainland. The ferry connections are plotted
in dashed lines on the map (Fig. 33.1). The numbers indicate the length of
the ferry connection in meters.
Fig. 33.1. The island kingdom of the Algos comprised the seven islands B, C,...,H.
The dashed lines depict ferry connections. The numbers indicate the lengths of the
ferry connections in meters. For example, one ferry cruised between the mainland
A and the island D, covering a distance of 700 m one-way
B. V¨ocking et al. (eds.), Algorithms Unplugged,
DOI 10.1007/978-3-642-15328-0
33,
c
Springer-Verlag Berlin Heidelberg 2011
326 Katharina Skutella and Martin Skutella
The Bridge Project of the Algos
Once in a while, during stormy weather, ferries capsized. Therefore, the Algos
decided to replace certain ferry connections by bridges.
In the first year, one of the seven islands was going to be connected to the
mainland by a new bridge. The Algos built a bridge of length 130 m between
A and H, since all connections from A to other islands are longer.
During the second year, they wanted to connect another island to the
mainland. Therefore, the construction of a bridge between A or H and another
island was taken into consideration. The Algos built the shortest possible
bridge of length 90 m between H and C.
In the third year, the construction of another bridge (starting from A, C,
or H) should connect a third island to the mainland. This time, the shortest
possible option was the bridge of length 110 m connecting B and C.
The status quo of the ongoing building project is shown in Fig. 33.2.As
you can see, the Algos were not yet ready with their project.
In the following years, the bridge of length 170 m between C and G, then
the bridge of length 70 m connecting F and G, next the bridge of length 80 m
from G to E, and finally the bridge of length 180 m connecting B and D were
built.
Finally, after seven years, all islands were connected to each other and to
the mainland by bridges. The bridge project was therefore completed.
The final bridge system of the Algos is shown in Fig. 33.3.
The Algos were delighted. The time and effort for building the bridges
had been enormous, but they were convinced that they had avoided the con-
Fig. 33.2. The status quo of the building project after three years. The islands B,
C, and H are already connected to the mainland
33 Minimum Spanning Trees 327
Fig. 33.3. The final bridge system of the Algos
struction of excessively long bridges as far as possible. The total length of all
bridges added up, as you can easily check, to exactly 830 m.
Building Bridges After the Hurricane
Shortly after the completion of the last bridge, a terrible hurricane swept over
the kingdom and completely destroyed the precious bridges. After recovering
from the shock, the Algos decided to construct a new bridge system. Again,
the bridges were supposed to connect all islands to each other and to the
mainland.
Due to the hurricane, there was a lack of building material. It was agreed
to first build a shortest possible bridge. Therefore, in the first year after the
hurricane, the bridge of length 70 m connecting F and G was built.
Also in the second year building material was scarce, so that the next
longer bridge of length 80 m from E to G was built.
According to this strategy, in the third year the bridge of length 90 m
between C and H was built. After the construction of these three bridges the
three islands E, F, and G and the two islands C and H were connected to each
other (see Fig. 33.4).
In the fourth year, the shortest connection that had not been realized yet
was the one of length 100 m between E and F. Because both islands were
already connected to each other via G, they instead built the bridge of length
110 m connecting B and C.
During the fifth year, the bridge of length 130 m from A to H was added,
then the bridge of length 170 m connecting C and G, and finally, in the seventh
328 Katharina Skutella and Martin Skutella
Fig. 33.4. The status quo of the second bridge project three years after the hurri-
cane. The bridge system consists of three bridges of lengths 70 m, 80 m, and 90 m.
The shortest connection that has not been realized yet is the one between E and F
(marked by a dashed line on the map). In the fourth year, however, the Algos de-
cided against building this bridge, because these two islands were already connected
to each other via G
Fig. 33.5. The second bridge system of the Algos
year, the bridge of length 180 m from B to D. The new bridge system of the
Algos is depicted in Fig. 33.5.
With great astonishment the Algos realized that despite their new strategy
in building bridges, they had ended up with the same bridge system of total
length 830 m (compare Fig. 33.3). This confirmed the Algos’ belief that they
33 Minimum Spanning Trees 329
had found the optimal bridge system for their islands. And unless no second
hurricane has made trouble ever since, the Algos stroll happily and proudly
over their bridges till today.
The Algorithms of Prim and Kruskal
Now you probably wonder, whether the Algos were rightly proud of their
bridge system. Perhaps, there is still a better, thus shorter bridge system?
Using trial and error you can find out that any other bridge system that
connects the seven islands and the mainland to each other is longer than
830 m.
A bridge system of minimum total length that connects several places (here
mainland A and islands B to H) to each other is called “minimum spanning
tree.” The problem of finding a minimum spanning tree has many different
practical applications aside from building bridges. For example, it arises when
planning the sewage system of a new housing estate. The goal is to connect all
estates to the sewage system at the lowest possible price. Other applications
are the design of computer chips and the planning of traffic or communication
networks (telephone, TV, internet, etc.).
Both strategies of the Algos exemplify well-known algorithms for solving
the problem. The first strategy is known as “Prim’s Algorithm.” This algo-
rithm connects places to the mainland one after another. In each step the
shortest possible bridge is being built.
Prim’s Algorithm
1 Choose a special place (mainland) and call it reachable.
2 Initially all other places are not reachable.
3 Repeat the following steps until all places are reachable:
Build the shortest bridge between two places, of which one is reachable
and one is not reachable, and call the one that had not been reachable
yet reachable.
The second strategy described above (after the hurricane) is known as
“Kruskal’s Algorithm.” This algorithm builds in each step the shortest bridge
connecting two places that have not been connected before. It differs from
Prim’s Algorithm in the way that it not only takes bridges establishing a
connection to the mainland into consideration, but allows for arbitrary bridges
connecting two places that have not been connected yet.
Kruskal’s Algorithm
Repeat the following step until all places are connected to each other through
bridges:
Build the shortest bridge that connects two places that are currently not yet reach-
able from each other.