There is a straightforward way to solve this:
- Run Dijkstra's for
V - H
, i.e. all nodes except those in H
. Let the output be dist
.
- 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.