Algorithmics - The Computing Universe: A Journey through a Revolution - page 93

Let us look at another important problem. This is the problem of finding
the shortest path through a graph - the sort of algorithm used by our GPS nav-
igation systems. How does the computer embedded in our GPS system solve
such problems? It does so by using a variant of the shortest path algorithm
devised by Edsger Dijkstra, an early computer science pioneer in the area of
programming languages and software engineering. Dijkstra was asked in an
interview how he came to invent his shortest path routing algorithm and he
replied:

A

10

30

B E

10

C D

20
Fig. 5.9. The cheapest solution connect-
ing all five cities with the minimum
length of optical fiber is the MST for the
graph in Figure 5.8 .b. In this case the
MST can be found using a simple greedy
algorithm, as explained in the text.

What is the shortest way to travel from Rotterdam to Groningen? It is the
algorithm for the shortest path which I designed in about 20 minutes. One
morning I was shopping with my young fiancée, and tired, we sat down
on the café terrace to drink a cup of coffee and I was just thinking about
whether I could do this, and I then designed the algorithm for the shortest
path. 4

Let us go back to our company in the New York area. Suppose that the com-
pany's headquarters are located in Newark (city A) and that it frequently needs
to deliver supplies from its headquarters to each of its offices located in the
communities of Manhattan (B), Yonkers (C), the Bronx (D), and Queens (E). For
simplicity's sake, let's assume that the edges of our graph are “directed” like
one-way streets, meaning they can only be traveled in one direction. In addition,
we need to ensure that there is no possibility of these directed edges forming a
closed loop or cycle; with our one-way restrictions this is true of the graph in
Figure 5.12 . This type of graph occurs in many places in computer science and
has the intimidating name of a Directed Acyclic Graph, or DAG.
To find the shortest path from the head office in Newark to every other
office, Dijkstra's algorithm uses a greedy method. Let us see how Dijkstra's
algorithm works in this case:

Fig. 5.10. An example of a tree structure
organization. The tree data structure
is one of the key concepts of computer
science and they are the cornerstones
of all databases. A tree consists of nodes
and branches. Whenever a node is added
or removed the tree needs to be adjusted
in order to make it shorter and more
“bushy” rather than tall and thin. This
makes search operations much faster.

• The first iteration of the algorithm starts at headquarters A and finds

the office that has the shortest direct connection to A. In our example
of Figure 5.8b , the closest office to A is clearly B, with the a distance of
10. (Note that because there is no direct connection from city A to office
C, we set distance to infinity.)
The next step in the algorithm examines the shortest paths to the other •

offices if we start from A as before, but also now allow the option of
going through B. We see that by going through B, we can now get to C
and therefore we record the distance as 10 + 50 = 60. For the next step
in the algorithm we need to add to our set of two locations, A and B,
the next closest office to A. The next shortest path is now to office D,
with a distance of 30.
For the third iteration we now allow paths from A that can either go •

directly from A or via locations B or D. With this extra option, we see
by inspecting the graph ( Fig. 5.8b ) that the shortest path from A to C is
now through D rather than through B. Similarly, it is now shorter to get
to E through D than going direct from A. Again, we complete the step
by looking for the city with the next shortest path from A, which is now
C with a distance of 50. Fig. 5.11. Cartoon of a self-adjusting tree.