algorithm - An graph algorithm

Question

There is a algorithm question which I really can't figure it out. The question may use Dijkstra algorithm.

There is a network of n computers that you will hack to take control. Initially, you have already hacked computer c0 . There are m connections between computers, through which you can use to take down an uncontrolled computer from a hacked one. Each connection is described as a triple (ca ; cb ; t), which means if ca is hacked, then you can successfully hack cb at a cost of t minutes.

A large group of your hacker friends join you in hacking (they are as good as you and as many as the computers in the network). They are all at your command, which means you can assign them hacking tasks on multiple computers simultaneously. Describe an ecient algorithm to determine how many minutes you would need to successfully hack all the computers in the network. State the running time in terms of n,m.

Answer 1

Let your computers are labeled as c_0, c_1, ..., c_{n - 1}. After you running Dijkstra the answer you are looking for is max { d[i] | 0 <= i <= n - 1} where d[i] denotes the minimum distance between c_0 and c_i. This is true because: 1) you at least need time equal to maximum of all those distances in order to hack the most distant computer 2) take a look at the tree we got after applying Dijkstra's algorithm (c_0 would be the root of that tree). We can apply the following strategy: first we start off hacking all the neighbors of c_0 and we continue with hacking all computers that have already been hacked. We do this until all the computers have been hacked. We can see that the time needed for this to happen would be equal to maximum depth of the tree (note that the edge of this tree have weight equal to those of the original graph). We can easily see that this is exactly the same number we mentioned before. So the total running time would is equal to Dijkstra's O(m + nlogn)