Information Technology Reference
In-Depth Information
•
For the next and final iteration, we calculate the shortest paths from
A
A to each other location, but now allowing any of the offices B, D, and
C as possible intermediate destinations. The shortest path to E is now
through offices B and C rather than through D or going direct from A.
B
E
In this way, we have now found the shortest path from A to all the other loca-
tions in the graph. These iterations of Dijkstra's algorithm are summarized in
Table 5.2
.
There are many other types of routing algorithms that can be applied to
such shortest path problems. One important method is called
dynamic program-
ming
, which is a technique that can be used when simple greedy algorithms do
not give the best solution. Dynamic programming algorithms allow for long-
range optimizations instead of the purely local optimizations performed in
Dijkstra's algorithm.
Before we leave this section, we want to introduce an important charac-
ter in the study of algorithmics and graph problems - the traveling salesman
problem, or TSP, which has fascinated mathematicians and computer scientists
since the 1930s. The problem can be stated as follows: given a list of cities and
the distances between each of them, what is the shortest route that a traveling
salesman can take to visit each city and return to his starting point?
Obviously one way of solving this problem is just to use brute force and
enumerate every possible route. For our five-location network in
Figure 5.8b
,
we can calculate how many different routes the salesman could take. The prob-
lem is equivalent to finding the number of permutations of the five symbols A,
B, C, D, and E. Because any shortest route starts and finishes at the same city,
using any of the five cities as the starting point of the route gives the same
answer. So we can just start with A and look for all the possible routes starting
with A. There are then four possible choices for the second city, three for the
third, and two for the fourth, before we are left with only the fifth city. Thus it
looks like we need to evaluate 4 × 3 × 2 × 1 = 24 permutations (or 4!, to use the
common notation for factorials). But there is another simplification. The dis-
tance from B to C is clearly the same as the distance from C to B, and the same
is true for every pair of cities. Each permutation has a reverse permutation of
the same length, and it does not matter which direction we travel round the
tour. We therefore need to consider only 4!/2 = 12 different routes.
The shortest path for this problem, ABECDA, is shown in
Figure 5.13
.
Where is the difficulty with the TSP? For an N-city problem, we need to exam-
ine (N - 1)!/2 tours, and as the number of cities increases, this brute force
C
D
Fig. 5.12. An example of a Directed
Acyclic Graph or DAG.
Table 5.2 Iterations of Dijkstra's algorithm. Column S is a set of cities used in the shortest
path search. D[node] is the distance to a city
Iteration
S
D[B]
D[C]
D[D]
D[E]
Initial
{A}
10
∞
30
100
{A,B}
10
60
30
100
#1
#2
{A,B,D}
10
50
30
90
#3
{A,B,D,C}
10
50
30
70
#4
{A,B,D,C,E}
10
50
30
70
Search WWH ::
Custom Search