Shortest path preview

Shortest path algorithms: BFS for unweighted graphs; Dijkstra for non-negative weights with priority queue; Bellman-Ford handles negative edges (preview).

Algorithm pick

BFS distances

#include 
#include 
#include 

int main() {
    std::vector> adj = {{1}, {0, 2}, {1}};
    std::vector dist(3, -1);
    std::queue q;
    dist[0] = 0; q.push(0);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u])
            if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
    }
    std::cout << "dist to 2=" << dist[2] << "\n";
    return 0;
}

Dijkstra idea

Greedy: always settle closest unvisited vertex; relax edges with priority queue—requires non-negative weights.

Topological sort preview

On a DAG, topological sort orders nodes so every edge u→v has u before v—Kahn's algorithm enqueues in-degree zero nodes (same BFS queue skills). Cycles make topo sort impossible.

Important interview questions and answers

1. Q: Why Dijkstra fails with negative edge?
   A: Settled distance can be improved later—breaks greedy invariant.
2. Q: BFS distance array?
   A: dist[v] = dist[u]+1 when first visit—shortest in unweighted graph.

Self-check

1. Which algorithm for unweighted shortest path?
2. Why priority queue in Dijkstra?

Pitfall: Dijkstra does not work with negative edge weights—say Bellman-Ford instead.