Indian National Olympiad in Informatics
Online Programming Contest, 2-3 April 2005
IARCS home > OLYMPIAD
Advanced Division
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-2024; Last Updated: 07 Sep 2005