Solution to Problem 1: Number Triples

Our first observation is that if there are two triples (a,b,c) and (a,b',c) with b ≤ b' then, we may safely drop the (a,b',c) triple as it will never appear in any shortest chain. Similarly, if (a,b,c) and (c,b',a) are triples with b ≤ b', we can safely drop (c,b',a) (Since in any chain using (c,b',a), we can replace it with (c,b,a) and get a chain of lower cost.) Suppose the given set of triples is: { (1,2,5), (5,2,6), (1,3,8), (8,1,11), (1,1,6), (10,1,6), (11,3,6), (10,4,8), (10,1,11), (6,4,5) } then, we may safely drop (6,4,5) since (5,2,6) is in the collection and get { (1,2,5), (5,2,6), (1,3,8), (8,1,11), (1,1,6), (10,1,6), (11,3,6), (10,4,8), (10,1,11) } Thus, without loss of generality, we may assume that for any pair of integers a,b there is at the most one triple of the form (a,b,c) in the given collection and if there is one then there is no triple of the form (c,d,a) in the collection. Let C be a given collection of triples. Let a_1, a_2, ... a_N be the set of integers that appear as the first or third coordinate in the given set of triples. We construct a graph with { a_1, a_2, ..., a_N } as the set of vertices. In this graph, add an edge connecting the vertices a_i and a_j if there is some d such that either (a_i,d,a_j) or (a_j,d,a_i) is in C and associate the ``weight'' d with that edge. For the list of triples listed above (after (6,4,5) was dropped) the resulting graph looks as follows: (1) ---------------------- | | | (2) (2) | 1 --------- 5 -------- 6 | / | | (3) / | | / | (3) | ----- 11 | (1) | / \ | | / (1) (1) \ | | / \ | 8 -------------------- 10 (4) where the vertices are { 1, 5, 6, 8, 10, 11 }. Each edge carries a weight (indicated inside brackets next to the edge). Formally a weighted graph is a graph equipped with a function wt which returns a integer for each edge in the graph. Such graphs are called weighted graphs. We shall write wt(a,b) to indicate the weight of the edge connecting a with b (only when there is an edge connecting a and b). Notice that a chain of triples corresponds to a sequence of edges in this graph. The cost of such a path, is the sum of the weights of the edges in the path. This is the same as the cost of the corresponding chain of triples. Thus, our task is to find the minimum cost path between a given pair of vertices. A minimum cost path is usually called the ``shortest path''. How does one represent a weighted graph? The obvious solution is to modify the adjacency matrix to store the weights. Thus we maintain a array of size N x N, where the (i,j)th entry stores the weight of the edge between vertex i and vertex j (Some special value (0 or -1 or MAXINT or ... ) is stored if there is NO edge connecting i and j). Given a weighted graph G=(V,E) with weight function wt and a pair of vertices S and T how do we find the shortest path connecting S and T? It turns out that given S and T, determining the shortest path from S to T is as difficult as finding the shortest path from S to every other vertex in the graph. So we shall focus on solving the latter problem. The idea is the following: Think of each vertex as an oil tank and the edges as oil pipes connecting them. The length of the pipe is the weight of the corresponding edge. Let us further assume that if there is a fire, the tanks burn instantaneously while it takes 1 second of time for the fire to move 1 unit of length through the pipes. So what happens when we set fire to the tank at S? The fire spreads via the pipes to all its neighbouring tanks, and from there via other pipes to their neighbours and so on. The time it takes for a tank T to catch fire is exactly the length of the ``shortest path'' from S to T (since the fire has been moving at 1 unit length per second). The algorithm due to E.W. Dijkstra uses this idea to determine the shortest path from S to all the other vertices. Of course, we don't build oil tanks and burn them, but simulate them using a program instead! We maintain two arrays of which one to keep track of which tanks have burnt already. The second one keeps track of when each vertex is expected to burn based on the status of the pipes attached to it (in particular, if there is no fire on any of the pipes leading to it, this value is taken to be infinity). We call the first array Burnt and the second as BTime. In each step, we determine the vertex that will catch fire next. Then, we update the second array to take into account that this change. Initially Burnt[S] is set to 1 and Burnt[V] is set to 0 for all other vertices. BTime[S] is set to 0 (since it already caught fire at time 0), for each neighbour V of S, BTime[V] is set to wt(S,V) and finally BTime[V] is set to infinity for all other vertices. At any point, how do we determine which vertex will be burnt next? We look through the BTime array to determine the unburnt vertex V for which the value of BTime[V] is minimum (and not equal to infinity) among all the unburnt vertices. That is the vertex that will burn next. We burn V by setting Burnt[V] to 1. Now that V has burnt (at time BTime[V]), the fire can spread from it through the edges to its neighbours. So, we update the Distance array to reflect the expected time of burning of the neighbours as: For each neighbour U of V BTime[U] = Minimum( BTime[U], BTime[V] + wt(U,V) ) If the fire heading towards U from some other vertex will reach earlier than that via V, we leave BTime[U] unchanged, or else we set it to the time that V burnt plus the time taken for the fire to reach U from V through the edge connecting them. Notice that when a vertex V is burnt, the time at which it is burnt is available in BTime[V]. Thus, the shortest path to any vertex T can be obtained from BTime[T] once T is burnt. If the smallest value in BTime among unburnt vertices is infinity that means that there is NO path from S to those vertices. Thus the algorithm can terminate if either all vertices are burnt or if the smallest value among unburnt vertices in BTime is infinity. Let us simulate this algorithm on the graph described above to find the length of the shortest paths from 1 to all the other vertices. Initially: i : 1 5 6 8 10 11 Burnt[i] : 1 0 0 0 0 0 BTime[i] : 0 2 1 3 Inf Inf Thus, we see that 6 is the vertex that will burn next. The time to burn for 10 and 11 is now set to 2 and 4 respectively. But the time to burn for 1 (it is already burnt) and 5 (it will burn at time 2 and via 6 the fire will reach it only at time 3) do not change even though they are neighbours of 6. Updating this information we get: i : 1 5 6 8 10 11 Burnt[i] : 1 0 1 0 0 0 BTime[i] : 0 2 1 3 2 4 The next vertex is burn is 10 (or 5, we could do it in any order as they both burn at the same time) and updating this information we get i : 1 5 6 8 10 11 Burnt[i] : 1 0 1 0 1 0 BTime[i] : 0 2 1 3 2 3 The next vertex to burn is 5 and we then get i : 1 5 6 8 10 11 Burnt[i] : 1 1 1 0 1 0 BTime[i] : 0 2 1 3 2 3 Then 8 burns to give i : 1 5 6 8 10 11 Burnt[i] : 1 1 1 1 1 0 BTime[i] : 0 2 1 3 2 3 and finally 11 burns to give i : 1 5 6 8 10 11 Burnt[i] : 1 1 1 1 1 1 BTime[i] : 0 2 1 3 2 3 The length of the shortest path from 1 to all the vertices in the graph is available in the array BTime[]. Here is the detailed algorithm: ============================================================== /* We assume that the Array E[][] contains the weights of the edges and that the value of E[i][j] is Infinity (something bigger than all integers) if there is no edge from i to j. We leave it to the reader to modify this algorithm without using Infinity */ for i=1 to N { Burnt[i] = 0; BTime[i] = Infinity; } Burnt[S] = 1; for each neighbour V of S { BTime[V] = wt[S][V]; } While (true) { If there are no Unburnt vertices GoTo Finished; Find the unburnt vertex i with minimum BTime[i]. If BTime[i] = Infinity GoTo Finished; Burnt[i] = 1; for j = 1 to N { /* For each vertex if the time taken via i is less than the current expected time then update */ /* Since Wt[i][j] is infinity if there is no edge we don't have to check whether there is an edge from i to j */ if (!Burnt[j]) { if (BTime[i]+Wt[i][j] < BTime[j]) BTime[j] = BTime[i]+Wt[i][j]; } } } Finished: Print out the lengths of the shortest paths from S to all the other vertices. ================================================================ How much time does this algorithm take? Note that the total number of interations of the while loop is not more than N, since one vertex is burnt in each iteration. Within this while loop: 1) Finding if there are unburnt vertices and determing the minimum BTime vertex amongst these take time proportional to N. 2) Once a vertex is burnt the for loop to update BTime takes time proportional to N. Thus, this algorithm takes roughly N*N steps to solve this problem. Exercise: Modify the above algorithm to not only determine the shortest path from S to T but also to print out such a shortest path. Directed Graphs: So far the graphs we have considered have all been undirected i.e. each edge connects two vertices and can be traversed in both directions. However, it is often necessary to consider graphs where edges begin at one vertex and end at another, so that, they can be traversed only in one direction. Formally a directed graph is a pair (V,E) where V is a set of vertices and E, the set of edges, is a subset of V x V. Here is an example: Let V={s,a,b,c} and let E = {(s,a),(s,b),(a,b),(a,c),(b,a),(b,c)}. Thus, it is possible to go from s to a but not the other way around. Also note that there may be edges in both directions as between the vertices a and b. Remember that these are two different edges. Directed graphs are drawn with the vertices laid out arbirarily and the directed edges represented by connecting the vertices with arcs or lines with arrow heads to indicate the directionality. The graph described above can be drawn as follows: --> a -- / ^ | \ / | | \ s | | -->c \ | | / \ | v / --> b -- Directed graphs can be represented using Adjacency Matrices exacly as in the case of undirected graphs --- the only differnece is that the matrix will no longer be symmetric. They can also be represented using adjacency lists, the only difference being, it is possible now that a vertex v may appear in the list corresponding to w even though w does not appear in the list corresponding to v. One can once again talk of paths (a sequence of distinct vertices v_1, v_2, ... v_k where for each i (v_i,v_{i+1}) is an edge) and so on. The DFS and BFS algorithms described for undirected graphs may be applied to directed graphs quite easily (once again taking care that edges are traversed only in one direction.) A weighted directed graph is a directed graph equipped with a weight function that assigns a integer (or rational or real ...) weight to each edge in the graph. One may ask for the shortest path (the minimum cost path) from S to T in a directed graph. It is easy to verify that the above algorithm works for directed graphs, exactly as it is, as long as the adjacency matrix correctly represents the edges and weights of the directed graph. We leave the verification of the details to the reader.

Copyright (c) IARCS 2003-2018; Last Updated: 07 Sep 2005