“Teleportation” across astro-haunted galaxies

Question

“Teleportation”: You have a teleporter that can take you from galaxy i to galaxy j.  Cost to teleport is given by c(i,j) > 0, which can be arbitrary.  Some galaxies are “astro-haunted” - this is specified by a matrix A, where A[i] can be 0 or 1 (1 means that that galaxy is “astro-haunted”).  Give a polynomial time algorithm that minimizes the cost of going from galaxy 1 to galaxy n, such that you pass through a maximum of m astro-haunted galaxies.  (You can assume that galaxies 1 and n are not astro-haunted.)

Answer 1

Notation: D (i,j,m) = shortest path from i to j using a maximum of  m astrohaunted galaxies

Recurrence Relation: D (i,j,m) = min { D (i,z,m-1) + D (z,j,0) for all z}

Base Case: D (i,j,0)

Base case can be solved simply by using All Pairs Shortest Path.  [See comment by Dirk41000 below.]

If a galaxy itself is astro-haunted, then APSP won't work for it, but we can use c(i,j) as the simple answer in that case.

So, D(i,j,0) = min {c(i,j); APSP of eliminating all AH galaxies}

Recursive Algorithm:

For m = 1 to k
  For i = 1 to n
     For j = 1 to n
       Calculate D(i,j,m) = min { D (i,z,m-1) + D (z,j,0) for all z}

Each calculation of D(i,j,m) takes O(n) time.

Time Complexity

Time Complexity of base case: O(n³)

Time Complexity of recursive portion: O(k * n³)

Total time complexity: O(k * n³)

Comments

B(i,j, k) is the base case, the modified APSP.  B(i,j,k) represents
the distance from i to j, using a set of nodes {1..k} as possible
intermediate nodes, and such that no astro haunted intermediate nodes
are allowed.

B(i,j,0) = c(i,j).
B(i,j,k) =
     min{B(i,j,k-1) , B(i,k,k-1) + B(k,j,k-1)}  if k is not astro haunted
     min{B(i,j,k-1)} if k is astro haunted
Then, B(i,j,n) is the base case, which we can use for D(i,j,0)

Answer 2

so A[i] = 1 means this galaxy can use teleportation? just get the shortest path in all of galaxy that A[i] = 1?

Answer 3

We observe that the problem is similar to all pairs shortest path problem, but in addition to that, we have the constraint that we can go through at most m astro-haunted galaxies. We model this constraint also in our notation.

Notation Let D(i,j,k) denote the cost of the shortest path from i to j using at most k astro-haunted galaxies.

Recursive Formulation Recursive formulation on D(i,j,k) can be written on the variable k and by deciding on the last astro-haunted galaxy on the path from i to j . D(i,j,k) = min { D(i,j,k-1), min (1≤z≤n | A[z]=1 ) {D(i,z,k-1) + D(z,j,0)} } We observe that A[z] = 1 constraint specifies that the galaxy z is astro haunted.

Further, by taking the minimum with D(i,j,k-1) we satisfy the constraint of at most k astro-haunted galaxies, while still avoiding pitfall of leaving this value undefined in case there is no astro haunted galaxy.

Base Case D(i,j,0) can be solved simply by using All Pairs Shortest Path and by eliminating all astro-haunted galaxies.

Algorithm The algorithm can easily be written in terms of for loops for each of the indices in the notation of D(i,j,k) . As is often observed, the index of the main recursive formulation usually forms the outermost loop.

// Step 1: Base Case

Calculate D[i][j][0] as All Pairs Shortest path by ignoring the astro haunted galaxies.

// Step 2: Inductive Step

for k = 1 to m

 for i = 1 to n

  for j = 1 to n

Calculate D[i][j][k] = min {D([i][j][k-1], D[i][z][k-1] + D[z][j][0] for all z such that A[z] = 1}

Time Complexity

Time Complexity of base case: O(n^3 ) from the all pairs shortest path problem. Each calculation of D(i,j,k) takes O(n) time. Further, there are kn^2 entries in the dynamic programming table. Therefore, the total time Complexity of recursive portion: O(k n^3) Therefore, the total time complexity is O(k n^3 ).