I\'m stuck on this problem, I think the algorthim will involve Dijkstra\'s algor
ID: 3671944 • Letter: I
Question
I'm stuck on this problem, I think the algorthim will involve Dijkstra's algorthim, or at least a variation of it.
You are an IT developer, who works in a company that produces robots. Your robots are designed to do certain work in a given area (for example, vacuum-clean a room). Each robot has a map of the area uploaded into its memory. The map is partitioned into rectangles, and at each moment any robot can either stay in its current rectangle or move to one of adjacent rectangles. If a charge of some robot fall below a critical level, and there is another robot in the area with a high charge, they should be programmed to meet so that one robot can recharge another robot. You are given a task to implement this feature. You are given a map and current rectangles of two robots as an input, and your algorithm should find a rectangle, where a meeting of robots can occur in a shortest possible time.
Represent this problem as an algorithmic problem on graphs. Propose an algorithm to solve this problem. What is its running time?
Explanation / Answer
function Dijkstra (Map,source)
{
create rectangle set R
for each rectangle r in Map {
dest[r] =INFINITY;
prev[r] = UNDEFINED;
add r to R
}
dest[source] = 0;
while (R !=EMPTY)
{
u <- rectangle in R with min dest[u];
remove u from R
for each adjacent r of u {
alt <- dest[u] + length(u,r);
if (alt < dest[r]) {
dest[r] = alt;
prev[r] = u;
} }
}
return dest[],prev[];
}
Running Time : O(R log (E/R))