Designing an algorithm given an undirected graph

Question

Problem: given an undirected graph G, a subset H of the vertex set V, (i.e. H is a subset of V) and a starting vertex s (s is in V).

Design an algorithm that finds the lengths of the shortest paths from s to all vertices such that the paths don’t go through any intermediate vertex in H (meaning that you can end at a vertex in H but you cannot go through any vertex in H.) (If no such path exists then set the length to ∞. All edges are the same length.)

(The output of the algorithm should be an array similar to the dist array of BFS and Dijkstra’s.)

Answer 1

There is a straightforward way to solve this:

1. Run Dijkstra's for V - H, i.e. all nodes except those in H. Let the output be dist.
2. For every node i in H, the shortest path will be of length min {dist[j] + w[i][j]}, where min is applied across nodes j in V-H (can be made efficient if we have an adjacency list instead of matrix).

So basically, with Dijkstra, find the shortest paths to nodes not in H. Then, the shortest path to nodes in H is simply the shortest extension from a node in V-H to itself. (And for nodes in H that are not directly connected to V-H, they'd have ∞ as question states).

Noticed per @jrook's comment that you mentioned all edges are of same length. Then BFS can be used instead of Dijkstra's as well.

---

Another solution is running BFS on a modified version of the graph:

• Remove all edges within nodes in H among themselves.
• Make the edges between nodes in V-H and H directed, with the direction being from V-H to H.
• Make all other edges (i.e. those between nodes in V-H) directed by adding a directed edge in both directions.

In this modified and directed graph, you can apply BFS or Dijkstra to find the shortest paths of desired condition.