Shortest Path with a Must-Visit Vertex

You’ve probably used Dijkstra’s algorithm to find the shortest path between two points in a graph. But what if you’re given an extra constraint: the path must pass through a specific vertex along the way? This is a surprisingly common problem — think GPS navigation with a mandatory stop, or a delivery route that must visit a warehouse before the final address.

Understanding the Problem

Given a weighted undirected (or directed) graph, a source vertex S, a destination vertex T, and a mandatory waypoint M — find the shortest path from S to T that passes through M.

Key Insight

Recall from the shortest path concept: for any node x that is part of the shortest path from u to v in a graph G, the following must be true:

shortestpath(u, v) = shortestpath(u, x) + shortestpath(x, v)

The proof of this relation is simple. If someone considers a path from u to x that is not the shortest, we can replace that path with the shortest path from u to x to get a better answer for the shortest path from u to v. Therefore, the paths from u to x and from x to v must each individually be shortest paths.

Designing Our Solution

Since M must be a part of our shortest possible path, we can say:

shortestpath(S, T) = shortestpath(S, M) + shortestpath(M, T)

So we divide our task into two parts to find the actual answer. We find shortestpath(S, M) and shortestpath(M, T) separately, and simply add these two values to obtain our final solution.

We can implement this by running two Dijkstra calls — one from S and another from M. Let the distance arrays found after each Dijkstra run be dists[] and distm[] respectively. Our answer will be:

dists[M] + distm[T]

typedef pair<int, int> pii;
typedef vector<vector<pii>> Graph;
const int INF = 1e9;

vector<int> dijkstra(const Graph& adj, int start, int n) {
    vector<int> dist(n, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int shortestPathViaMid(const Graph& adj, int n, int src, int mid, int dst) {
    vector<int> dists = dijkstra(adj, src, n);
    vector<int> distm = dijkstra(adj, mid, n);

    if (dists[mid] == INF || distm[dst] == INF) return -1;
    return dists[mid] + distm[dst];
}