Graph Theory37 sections · 1633 units
Open in Course

CSES 1202 Investigation - Counting During Dijkstra

(Four arrays)

Run Dijkstra while maintaining four arrays:

1.1. dist[u] = shortest distance to u.

2.2. cnt[u] = number of shortest paths to u.

3.3. minEdges[u] = minimum edges on a shortest path to u.

4.4. maxEdges[u] = maximum edges on a shortest path to u.

Update all four arrays together during edge relaxation. This tracks multiple properties in a single Dijkstra pass. Initialize: dist[1]=0, cnt[1]=1, minEdges[1]=0, maxEdges[1]=0, and infinity or zero for all other nodes.