Sunday, September 6, 2009

423 - MPI Maelstrom - UVA

graph algorithms - single source shortest path Dijkstra

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