You are on a battlefield where the enemy ranks have established n bases. A recen

Question

You are on a battlefield where the enemy ranks have established n bases. A recent wave of spies infiltrated the bases and were able to radio back some information about the enemy forces. They informed you that the enemy has either 1, 2, or 3 platoons of soldiers guarding each base. Moreover, one of the spies lets you know which base is housing the enemy flag!

This flag is inexplicably important and capturing it means victory for your side. For this mission, you are given charge over a large brigade of soldiers to invade the enemy bases and capture their flag. You can choose how your brigade travels from base to base, though there are a limited number of roads connecting the bases and your soldiers can only travel on these roads. These roads are one-way in the sense that going the wrong way on any of these roads would give too much of a strategic advantage to the enemy to be a viable option (i.e. you can think of this as a directed graph).

Design an algorithm that finds a path through the bases for your brigade that minimizes the number of enemy platoons encountered. The starting point for your brigade is fixed, and the path should end at the enemy flag. You only have to capture this flag, not visit every base. Once your soldiers arrive at the flag the battle will be over, so don't worry about an extraction plan.

There are n bases and m roads connecting the bases.

You must design an algorithm to find the a path in O(m+n) time that minimizes the number of enemy platoons encountered. An O(mlog n) time algorithm would be ok, but an O(m+n) time algorithm is ideal. For full credit, an O(m + n) runtime algorithm must be given. No need for a formal proof of correctness, but you must give an argument for the runtime.

Explanation / Answer

Shortest path alogoorithm helps you in this situation.
Concept:
Shortest Path algorithm to find the distance
with an order of O(m+n)

Shortest path alogoorithm helps you inn this situation.
Concept:
Shortest Path algorithm to find the distance
with an order of O(m+n)

Algorithm

Graph g
Source s
top_sorted_list = top_sort(g)

cost = {}

for each vertex v in top_sorted_list:
cost[vertex].cost = inf
cost[vertex].parent = None

cost[s] = 0

for each vertex m in top_sorted_list:
for each edge n in adjacenies of m:
if cost[n.dest].cost < cost[m].cost + n.weight:
cost[n.dest].cost = cost[m].cost + n.weight
   cost[n.dest].parent = m

Explanation:
by using this ,we can calculate shortest distances in
O(m+n) time using Shortest path algorithm.

In our scenario we have to reach each enemy plattons

this start point is fixed and the path will be stopped at enemy point.
  

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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