← all categories

Lex Smallest Path 3174cc67

Lexicographically smallest walk from x to y in an unweighted graph: greedily extend to the smallest-labeled unvisited neighbor that still has a path to y avoiding already-visited nodes.

Time: O(V(V + E)) worst case (one reachability BFS per step taken). tested

content/graphs/lex-smallest-path.h

vector<int> lexSmallestPath(int n, vector<vector<int>> &adj, int x, int y) {
    for (auto &nbrs : adj) sort(nbrs.begin(), nbrs.end());
    vector<bool> vis(n, false);
    vector<int> path = {x};
    vis[x] = true;
    int at = x;

    auto reachable = [&](int st, int en) {
        vector<bool> vis2(n, false);
        queue<int> q;
        vis2[st] = true;
        q.push(st);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (u == en) return true;
            for (int v : adj[u]) if (!vis[v] && !vis2[v]) { vis2[v] = true; q.push(v); }
        }
        return false;
    };

    while (at != y) {
        for (int v : adj[at]) {
            if (!vis[v] && reachable(v, y)) {
                vis[v] = true;
                path.push_back(v);
                at = v;
                break;
            }
        }
    }
    return path;
}