In this problem you face a communication system, that in this system messages are sent from station 1 to all other n-1 stations, there are costs to send messages from station 'a' to station 'b' if it's possible to send directly otherwise you have to find a route from station 1 to that station.

Since there are communication costs, sometimes it's better to send a message from station 1 to station 'b' not directly to minimize the cost to send message from station 1 to station 'b'.

In this manner each station will have a minimum time required to receive the message from station 1. This problem wants the maximum of these minimum times.

I use dijkstra to solve this problem. Let me explain what I do in my solution.

I have an adjacency matrix[101][101] and an array MIN[101] and a boolean array mark[101]

I construct adjacency matrix from input.

I initialize MIN[i] = infinity for i = 1 to n and MIN[1] = 0

and initialize mark[i] = false for i = 1 to n

I am going to construct a shortest path tree starting at node 1 using dijkstra. I have a node "current". Initially I set it to 1.

Then I check the adjacency matrix for node current and set

MIN[ neighbor[cur] ] = minimum( MIN[neighbor[cur]], MIN[cur] + adjMAT[cur][i] )

after checking all of the current neighbors I set mark[cur] = true and find a new current. how?

I check all of the nodes and from them that haven't been marked yet and has the minimum distance to node start I pick my next "current" node.

Since the graph is connected and has just one component I iterate through MIN[i] and pick the maximum.

## No comments:

## Post a Comment