You have an army of n robots at your disposal that you can program to collective

Question

You have an army of n robots at your disposal that you can program to collectively do various tasks. The robots use wireless communication to communicate with each other. Two robots are connected if they are within a distance d (range of wireless device) of each other. Thus, as the robots move around the territory, the robot network (graph) is changing. You want the robot network to stay connected while individual robots explore as much of the “territory" as possible. You have come up with the following rule: At any given time, each robot must be able to communicate with at least n/2 other robots.

Given a graph G that is comprised of a vertex set V = {V1, V2, V3, V4, …, Vm} and edge set E = {E1, E2, E3, …, En} with weights {W1, W2, W3, …, Wn}, write an algorithm that determines at any point in time whether your rule is satisfied. What is the time complexity of the algorithm?

Explanation / Answer

This scenario asks for distance matrix of each robot with every other robot.
We have to find distance between a&b for all possible a&b's.
floyd warshall algortihm is very standard for this kind of problems.

Time complexity of Floyd Warshall is O(|V|^3)

I'm providing pseudo-code of floyd-warshall

dist[n][n] array define with weights given if edge exists otherwise 0 values /* n is number of vertices

for(i=0;i<n;i++){

for(j=0;j<n;j++){

for(k=0;k<n;k++){

   if(dist[i][j] > dist[i][k]+dist[k][j])

     update dist[i][j]

}

}

}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.