Solution to Problem 2: The Great Escape

With this problem begins our first foray into what is called Graph Theory. More about that later. We say that a pair of buildings B_1 and B_2 are adjacent if the director has determined that it is possible to jump from B_1 to B_2 (and vice versa). We know the building the hero starts his search from. Call this building B and set S_0 = { B } and clearly every building in S_0 is reachable in 0 steps by the hero. The set of buildings that can be reached in a single step can computed as follows. It is the set of buildings that are adjacent to B. Call this set S_1. What about buildings that can be reached in 2 jumps (and not in fewer than 2 jumps)? Every such building must be adjacent to some building in S_1. However, not all buildings adjacent to buildings in S_1 will be in S_2 (since they may already be in S1 or S0). For example, if we had 4 buildings B, C, D and E and the following pairs are adjacent: B C B D C D D E Then, S_0 = { B } and S_1 = { C,D }. Now, the buildings C, D, B, and E have buildings in S_1 adjacent to them. However, since B, C and D are already present in S_0 U S_1 (where U denotes the union of sets), S_2 is the set { E }. In general let S_i be the set of buildings that can be reached from B by i jumps but not in i-1 or fewer jumps. Then, S_0 = { B } S_i = { C | C is adjacent to some building in S_{i-1} and C is not in S_0, S_1, ... S_{i-1} } So, we can compute S_0, S_1, ... in that order. When do we stop? Since S_i contains only buildings that do not belong to S_0, S_1, ... S_{i-1}, we will soon run out of buildings and for some k, S_k will be empty. As a matter of fact, k <= n if n is the number of buildings. If S_k is empty then there are no buildings that are reachable in k steps but not fewer. This in turn means that there are no buildings that are reachable in k+1 steps and not fewer and so on (Why?) To illustrate this, consider the set of buildings B,C,D,E,F,G,H with adjacency given by: B C B D C D D E F G H G F H Then S_0 = { B } S_1 = { C,D } S_2 = { E } S_3 = { } Thus, the buildings F,G and H are not reachable from B. C and D are reachable in 1 step and E in two steps. Now, how do we program this? Let the buildings be 1 ... n. We keep an array D with D[i]=j indicating that "i belongs to S_j" or in other words indicating that building i is at distance j from the starting building. We also assume that there are e adjacency relations and they are stored in a two dimensional array E. That is, E is a two dimensional array and The buildings E[i][1] and E[i][2], for i=1, 2, ... e are deemed to be close by the director. So our above example with buildings B,C,D,E,F,G and H would now consist of buildings 1,2,3,4,5,6,7 and the array E looks like: 1 2 1 3 2 3 3 4 5 6 7 6 5 7 where the first entry on row i is E[i][1] and the second entry is E[i][2]. We now describe the algorithm to compute the shortest distance from building b to all the other vertices. for (i = 1 to n) D[i] = MAXINT /* we use MAXINT > n to denote "undefined" */ D[b]=0 /* We start at building b and it belongs to S0 */ for (i=1 to n) { /* compute S_1,S_2,...,S_n */ for (j=1 to e) { /* Check if each adjacency relation connects a building in S_{i-1} to a building that is not in S_0,...S_{i-1} Update S_i appropriately */ if ((D[E[j][1]] == (i-1) ) && (D[E[j][2]] == MAXINT)) D[E[j][2]]=i /* You have found an as yet unvisited building that is adjacent to an building in S{i-1}, so put that in Si */ if ((D[E[j][2]] == (i-1) ) && (D[E[j][1]] == MAXINT)) D[E[j][1]]=i /* You have found an as yet unvisited building that is adjacent to an building in S{i-1}, so put that in Si */ } } If the target is to reach building t, then D[t] gives us the length of the shortest sequence of jumps that takes the hero to building t. If D[t] is MAXINT then there is no route by which the hero can reach the target. Observations: 1) The above algorithm determines the shortest path from b to every building and not just t!! 2) It also determines which buildings are reachable eventually and which are not. The structure of the above algorithm suggests that it takes roughly n * e steps where n is the number if buildings and e is the number of edges. We can do significantly better, in pariticular this problem can be solved in roughly e steps. Before we describe that solution, we want to introduce the terminology of graph theory for future reference. A graph, say G, consists of two sets, a set of vertices or nodes (V) and a set of edges (E). The set of vertices could be given finite set. Each edge is a set consisting of two vertices. We may interpret the set of edges as describing which pairs of vertices are "neighbours". The buildings and close pairs define a graph. We take the set of buildings to be the set of vertices and the set of edges consist of all those pairs of vertices that the director has deemed fit. The example with 7 vertices (1,2,...,7) is denoted by the graph G = (V,E) where V = { 1,2,3,4,5,6,7 } E = { {1,2},{1,3},{2,3},{3,4},{5,6},{5,7},{6,7} } It is often convenient to draw graphs with boxes or circles to represent the nodes and lines/curves connecting boxes/circles to denote edges: --- --- --- | 1 |---------| 2 | | 7 | --- /--- /---\ | / / \ | /-----/ / \ | / / \ ---/ --- ---/ \ --- | 3 |--------| 4 | | 5 |------------| 6 | --- --- --- --- Note that the placement of the boxes or the style of drawing the edges are irrelevant. The "real" graph is given by the two sets V and E and the picture is just to help us think. A path in a graph is a sequence of vertices v1,v2,...,vk such that {v1,v2}, {v2,v3} ... {v{k-1}vk} are edges. For example, 1,2,3,4 is a path in the above graph. The length of a path is the number of edges in the path. For example, the length of the path 1,2,3,4 is 3. The solution to the hero problem described above is actually a solution to the following general problem on graphs: given a vertex u, find the length of the shortest path from u to every other vertex v in the graph. And the solution recast in terms of arbitrary graphs reads as follows (and see that all I have to do replace the word "building" by vertex and so on ..) We assume that there are n vertices 1...n and e edges. We assume further that the edges are stored in a two dimensional array E, so that if E[i][1]=a and E[i][2]=b then {a,b} is an edge in the graph. for (i = 1 to n) D[i] = MAXINT /* we use MAXINT > n to denote "undefined" */ D[b]=0 /* We start at vertex b and it belongs to S0 */ for (i=1 to n) { /* compute S_1,S_2,...,S_n */ for (j=1 to e) { /* Check if any edge connects a vertex in S_{i-1} to a vertex that is not in S_0,...S_{i-1} Update Si appropriately */ if ((D[E[j][1]] == (i-1) ) && (D[E[j][2]] == MAXINT)) D[E[j][2]]=i /* You have found an as yet unvisited vertex that is adjacent to a verted in S_{i-1}, so put that in S_i */ if ((D[E[j][2]] == (i-1) ) && (D[E[j][1]] == MAXINT)) D[E[j][1]]=i /* You have found an as yet unvisited vertex that is adjacent to a vertex in S_{i-1}, so put that in S_i */ } } A vertex i is reachable from the vertex b (i.e. there is a path starting at vertex b and ending at vertex i) if and only if D[i] is not MAXINT. And if it is reachable then D[i] is the length of the shortest path from b to i. Note: The above algorithm is called a Breadth-First Search algorithm (or BFS) as unravels the graph level by level, where level i consisting of all the vertices at distance i from b. This is in contrast to a different algorithm called Depth-First Search. Is the above algorithm the best we can do? The inner loop which constructs S_i from S_{i-1} examines every edge. Is that necessary? After all, elements of S_i are those unvisited vertices (i.e. vertices that do no belong to S0, ... S{i-1}) that are connected by an edge to some vertex in S_{i-1}. So it should suffice to examine all the vertices that are connected by edges to vertices in S_{i-1}. In other words, it should be enough to consider only those edges that connect element of S_{i-1} to other vertices. If edges are stored in the array E as assumed in the earlier solution, then it is not possible to examine the just this subset without scanning through the entire array E. The idea is to store the edges in what is called an "Adjacency Matrix". Given a graph G with vertices 1,...,n, the edges of the graph can be represented by a 2 dimensional array (or equivalently a (n x n)-matrix) A defined as follows: A[i][j] = 1 if vertex i and vertex j are connected by an edge A[i][j] = 0 otherwise. Observation: If A[i][j] is 1 then A[j][i] will also be 1 (Since our edges are subsets are undirected. i.e. an edge {i,j} and we can use this to go from i to j as well as from j to i). With this we rewrite the above algorithm as follows: for (i=1 to n) for (j=1 to n) A[i][j]=0 /* Initialize the adjacency matrix*/ for (i=1 to e) { /* set the adjacency matrix based on E A[E[i][1],E[i][2]]=1; if {a,b} is an edge set A[a][b]=1 A[E[i][2],E[i][1]]=1; and A[b][a]=1 */ } for (i = 1 to n) D[i] = MAXINT /* we use MAXINT > n to denote "undefined" */ D[b]=0 /* We start at vertex b and it belongs to S0 */ for (i=1 to n) { /* compute S1,S2,...,Sn */ for (j=1 to n) { /* scan vertices to find vertices if (D[j] is i-1) in S{i-1} */ { /* found one. look for its unvisited neighbours*/ for (k=1 to n) { if (A[j][k] == 1) and (D[k]==MAXINT) /* Found one, so put it in Si */ D[k]=i } } } } How much time does this take? The initialization takes time roughly proportional to e + n*n. And now we have three levels of nested loops and this is going to take roughly n*n*n steps and so we get e + n*n + n*n*n which is roughly n*n*n (since e is not more than n*n). Well, that is clearly not better than n*e which can in the worst case be n*n*n!!! What we needed to do was to directly identify the elements of S_{i-1} (WITHOUT scanning the entire list of vertices) and then for each such vertex find the list of neighbours (WITHOUT scanning through the entire list of edges). The adjacency matrix offers a solution to the second problem but not to the first. Consider the following graph with 7 vertices: G = (V,E) where V = { 1,2,3,4,5,6,7 } E = { {1,2},{1,3},{2,3},{3,4},{3,6},{4,7},{6,5} } Here, starting at vertex 1 we get S0 = { 1 } S1 = { 2,3 } S2 = { 4,6 } S3 = { 7,5 } S4 = { } The order in which we "visit" the vertices is <1 2 3 4 6 7 5> and this sequence breaks nicely into S0,S1,... as {1}{2,3}{4,6}{7,5}. This is not an accident and will always happen since we visit all the elements of S_{i-1} before visiting the elements of S_i. Moreover when we intend to explore the neighbours of a vertex v in this sequence, we would have already explored all the neighbours of all the vertices that appear before it in the sequence. Thus, if we keep track of the sequence in which vertices have been visited and the last vertex whose neighbours have been explored we can determine the next vertex whose neighbours need to be explored. Intially we have the sequence <1> and nothing is explored. So we examine the neighbours of 1 and find that 2 and 3 are its neighbours and we add them to the list to get <1.2 3> where I have placed a . after 1 to indicate that 1 is the last vertex whose neighbours have been explored. We examine the neighbours of 2 next and get <1 2.3 > (since the only neighbour of 2 is 3 and it is already in the list.) Considering 3 next we get <1 2 3.4 6> and then <1 2 3 4.6 7> and then exploring neighbours of 6 we get <1 2 3 4 6.7> and finally exploring the neighbours of 7 we get <1 2 3 4 6 7 5.> and now there is nothing more to explore. Observe that we need not carry along the vertices to the left of the . as they play no further role. Thus, we can simply drop the vertices to the left of the . in all these sequences. Thus, we begin with <1>, exploring the neighbours of 1 we get <2 3> then exploring the neighbours of 2 we get <3> and then exploring the neighbours of 3 we get <4 6> and then <6 7> followed by <7> and finally <>. The way updated the sequences above has the following feature: we add elements to the right and delete elements from the left. This similar to what happens at the queue at a railway counter or a cinema ticket counter. You enter at one end and leave from the other. Thus, we need to keep the vertices in a queue, pick the one at the head of the queue, explore its neighbours and and add any unvisited ones to the tail of the queue and then delete the head of the queue. We can use an array Q and two integer variables H (for head) and T (for tail) to do this as follows: For instance the queue <2 7 6 3> would be represented by i : 1 2 3 4 Q[i]: 2 7 6 3 H = 1 and T = 4 Now, if we add 4 to this queue, we will store it position T+1 (5) and increment T to 5 to get: i : 1 2 3 4 5 Q[i]: 2 7 6 3 4 H = 1 and T = 5. Now if we delete an element from the head of this queue, the resulting queue would look like: i : 1 2 3 4 5 Q[i]: 2 7 6 3 4 H = 2 and T = 5. Now if we add an element say 1, we would get: i : 1 2 3 4 5 6 Q[i]: 2 7 6 3 4 1 H = 2 and T = 6. At any point the queue consists of the elements Q[H],Q[H+1] ...Q[T]. Q[H] is at the head of the queue and Q[T] is at the tail. How is the empty queue represented? Simple, set Tn to denote "undefined" */ H = 1 T = 0 /* Initialize the queue to be empty */ D[b]=0 /* We start at vertex b and it belongs to S_0 */ Q[T+1]=b T=T+1 /* Insert b as the first element of the Queue*/ While ( T >= H ) { /* As long as the queue is not empty */ j = Q[H] /* Let us pick the first vertex in the queue i.e. the one at the head of the queue */ for (k=1 to n) { /* See if it has unvisited neighbours */ if (A[j][k] == 1) and (D[k]==MAXINT) { /* Found one */ /* Since j belongs to S_{D[j]} k must belong to S_{D[j]+1}. Update D[k] to indicate that*/ D[k]=D[j]+1 /* and insert it at the tail end of the queue*/ Q[T+1]=k T=T+1 } } H = H+1 /* Since the neighbours of j have been considered delete j from the queue } How long does this algorithm take? Notice that the inner "for" loop is executed for a vertex j only when it is at the head of the queue. Each vertex in the graph can be at the head at the most once (If it ever enters the queue it will be at the head exactly once and then it will be deleted from the queue). Thus the inner for loop is executed at the most once for each vertex in the graph and so the number of steps taken by this algorithm is roughly n*n steps. This is a significant improvement on n*n*n as well as n*e (since e can be as large as n(n-1)/2). Can we do better? One place where we could optimize is the inner for loop. To explore the neighbours of j we look at every vertex k and check if it is a neighbour of j and then if it has been visited. If we could somehow keep track of the neighbours of j then we only need to examine whether each neighbour has been visited. It turns out that this can be done and the resulting algorithm takes roughly e steps. We postpone a description of that idea to a different day.

Copyright (c) IARCS 2003-2020; Last Updated: 15 Mar 2005