Exercises — Dijkstra's algorithm — greedy, priority queue, O((V+E) log V) — no negative edges

Dijkstra requires every edge weight to be $\ge 0$ (non-negative). A weight of $0$ is fine.

• (a) ✓ all equal $3\ge 0$.
• (b) ✓ includes $0$, that is allowed.
• (c) ✗ has $-1$, a negative edge — the correctness proof's "$\ge 0$" step dies.
• (d) ✓ zeros are allowed. Answer: a, b, d. For (c) you would use Bellman-Ford algorithm.

BFS. When every edge costs the same, "closest by weight" = "fewest edges", which is exactly what BFS explores layer by layer. BFS runs in $O(V+E)$ — no heap, no $\log V$ factor. So don't pay for Dijkstra's priority queue when you don't need weights.

False. A vertex is finalized only when it is popped with a non-stale distance (recall: an entry $(d,u)$ is stale when $d>dist[u]$, meaning a better route was found after this entry was pushed). Between a push and its pop, a cheaper route may still be found, lowering $dist[v]$. Finalizing at push time is a classic bug.

Recall from the setup: $\infty$ means "no route yet", and a relaxation succeeds only when $dist[u]+w$ is strictly less than the current $dist[v]$.

Line-by-line, why each relaxation succeeds or fails:

• Step 1, pop A(0). $C$ and $B$ still hold $\infty$. Relaxing $A\to C$: $0+1=1<\infty$ — succeeds (any finite number beats $\infty$), so $dist[C]=1$. Relaxing $A\to B$: $0+4=4<\infty$ — succeeds, $dist[B]=4$.
• Step 2, pop C(1) (we pop $C$ before $B$ because $1<4$ — the heap always yields the minimum). Relaxing $C\to B$: $1+2=3$, compared to the current $dist[B]=4$; since $3<4$ it succeeds, lowering $B$ from $4$ to $3$. Relaxing $C\to D$: $1+5=6<\infty$ — succeeds, $dist[D]=6$.
• Step 3, pop B(3). Relaxing $B\to D$: $3+1=4$, compared to the current $dist[D]=6$; since $4<6$ it succeeds, lowering $D$ from $6$ to $4$.
• Step 4, pop D(4). $D$ has no outgoing edges, so there is nothing to relax — the run ends.

Final: $A=0,B=3,C=1,D=4$. Key moment: after step 1 the heap holds B(4) and C(1); we pop the minimum C(1), and that is what makes the $C\to B$ relaxation in step 2 available, dropping $B$ from 4 to 3.

Recall $prev[v]$ from the setup: the vertex we arrived from on $v$'s current best route. It starts as $\text{nil}$ for every vertex, and each successful relaxation of $u\to v$ sets $prev[v]=u$ (it is updated in lock-step with $dist[v]$). Reading off the successes from the L2.1 trace:

• $D$'s last successful relaxation was $B\to D$ in step 3 ⇒ $prev[D]=B$.
• $B$'s last successful relaxation was $C\to B$ in step 2 ⇒ $prev[B]=C$.
• $C$'s successful relaxation was $A\to C$ in step 1 ⇒ $prev[C]=A$.
• $prev[A]=\text{nil}$ (the source has no parent) — this is where the trace-back stops. Follow the parents backwards from the target: $D\leftarrow B\leftarrow C\leftarrow A$, then reverse. Path: $A\to C\to B\to D$, total $1+2+1=4$. ✓ matches $dist[D]=4$.

When we pop A(0) we now also relax $A\to D$: $0+4=4<\infty$ — succeeds, so $dist[D]$ becomes $4$ immediately (and $prev[D]=A$). Later, the route $A\to C\to B\to D$ also totals $4$. When step 3 tests $B\to D$: $3+1=4$, compared to the current $dist[D]=4$; since $4\nless 4$ the relaxation fails — it's a tie, so $dist[D]$ stays $4$ and $prev[D]$ stays $A$. No distance changes. (The recovered path may differ depending on tie-breaking, but the cost is identical.)

Take vertices $s,A,B$ with edges s→A(2), s→B(1), B→A(-3). True shortest to $A$: $s\to B\to A=1+(-3)=-2$ (cheaper than the direct $s\to A=2$). Dijkstra's run:

• Pop s(0), relax $A=2$, $B=1$. Heap {B(1), A(2)}.
• Pop the minimum B(1), finalize it. Relax its edge $B\to A$: $1+(-3)=-2<2$ ⇒ $dist[A]=-2$ and we push A(-2). Heap {A(-2), A(2)}.
• Pop A(-2), finalize $A=-2$.

With this ordering Dijkstra actually recovers $-2$. To force the wrong answer we need the negative edge to point into an already-finalized vertex. The genuine failure is drawn in Figure 2 below: s→X(1), s→Y(2), Y→X(-5).

• Pop s(0), relax $X=1$, $Y=2$. Heap {X(1), Y(2)}.
• Pop X(1), finalize $X=1$ — done forever.
• Pop Y(2), relax $Y\to X$: $2+(-5)=-3<1$, but $X$ is already finalized; a correct Dijkstra never re-pushes/re-finalizes it.
• Wrong finalization: $X=1$, while the true distance is $s\to Y\to X=2+(-5)=-3$. The "$\ge 0$" step of the proof is exactly what fails: the tail edge $Y\to X$ is negative, so a longer-hop path became cheaper after $X$ was declared done.

Keep the two quantities separate — they are different things.

• (i) Cumulative pushes/pops over the run. Each successful relaxation pushes exactly one new pair, and there are at most $E$ successful relaxations total (each directed edge $(u,v)$ can relax $v$ only when $u$ is finalized), plus the one initial push of $s$. So the run performs $O(E)$ pushes and hence $O(E)$ pops. Each push or pop costs $O(\log (\text{heap size}))$.
• (ii) Peak (instantaneous) heap size. At any moment the heap can contain at most every entry ever pushed and not yet popped, so it is bounded by the total pushes: $O(E)\le O(V^2)$. Therefore $\log (\text{heap size})\le \log (V^2)=2\log V=O(\log V)$.

Combining: $O(E)$ operations each costing $O(\log V)$ gives $O(E\log V)$.

• The $V$-term. Separately, we must create and set up the $dist[]$ array (and $prev[]$) with one entry per vertex — that is $O(V)$ work, independent of the heap. This array initialization is the only source of the standalone $V$ in the bound.

Total: $O(V)+O(E\log V)=\boxed{O((V+E)\log V)}$.

Same $dist[]$: with unit weights, minimum-weight path = fewest-edges path, which is exactly BFS's layers. Cost: BFS is $O(V+E)=O(11)$; Dijkstra is $O((V+E)\log V)=O(11\log 5)$. Dijkstra is a factor of $\Theta (\log V)$ slower. Use BFS here.

Skeleton is identical: min-heap, pop closest unfinalized vertex, relax neighbors.

• Dijkstra relaxes with dist[u] + w(u,v) — the accumulated distance from the source. It computes shortest paths (SSSP).
• Prim relaxes with just w(u,v) — the single edge cost to attach $v$ to the tree. It computes a Minimum Spanning Tree (MST). One term (dist[u] +) is the entire difference.

With $h\equiv 0$, A* orders the queue purely by $dist[v]$ — it reduces exactly to Dijkstra. For correctness, $h$ must be admissible: $h(v)\le$ (true remaining distance from $v$ to the goal), i.e. it never overestimates. An admissible $h$ only reorders exploration toward the goal without ever finalizing a vertex too early.

Johnson reweights every edge to be non-negative while preserving which path is shortest. It:

1. Adds a virtual source connected to all vertices with weight-0 edges.
2. Runs Bellman-Ford algorithm once to get a potential $h(v)$ (shortest dist from the virtual source).
3. Reweights each edge: $w^{\prime }(u,v)=w(u,v)+h(u)-h(v)\ge 0$.
4. Runs Dijkstra from every vertex on the reweighted (now non-negative) graph, then subtracts the potentials back out. This gives all-pairs shortest paths while still using fast Dijkstra.

It terminates. After $A$ is finalized at $5$, relaxing gives $B=5$, then $C=5$, then the edge $C\to A$ tries $5+0=5$, which is not $<dist[A]=5$. Relaxation fails, no push, no loop. Zero-weight cycles are safe because relaxation only fires on strict improvement. (Only negative cycles cause infinite improvement — and Dijkstra forbids negative edges anyway.)

Stop the instant $t$ is popped (with a non-stale distance) — at that moment $dist[t]$ is provably final by the greedy invariant. You cannot stop at push time: after $t$ is pushed with some value, a later-popped vertex closer to $s$ might relax $t$ to something smaller. Only the pop guarantees no smaller route survives, because every unfinalized vertex still in the heap has $dist\ge dist[t]$ and all edges are $\ge 0$.

Add a counter array $cnt[]$ initialized with $cnt[s]=1$ and $cnt[v]=0$ for all other $v$. During relaxation of edge $(u,v,w)$, compare the candidate distance $dist[u]+w$ against the current $dist[v]$:

• Strictly better ($dist[u]+w<dist[v]$): we found a new cheaper best, so the old count is obsolete ⇒ set $dist[v]=dist[u]+w$ and reset $cnt[v]=cnt[u]$.
• Equal — a tie ($dist[u]+w=dist[v]$): another shortest route arrived, so ⇒ add $cnt[v]+=cnt[u]$ (do not change $dist[v]$).
• Worse ($dist[u]+w>dist[v]$): change nothing.

The count is only trustworthy once $v$ is finalized (popped), since more ties may still arrive from vertices with equal $dist$. On the L2.3 graph, the shortest routes to $D$ (both cost $4$) are $A\to C\to B\to D$ and the direct $A\to D$, so $cnt[D]=2$.

Pushes $\le E=\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\Theta (n^2)$. Each heap operation is $O(\log V)=O(\log n)$. Running time $O((V+E)\log V)=O(n^2\log n)$. On a dense graph a Fibonacci heap wins: $O(E+V\log V)=O(n^2+n\log n)=O(n^2)$, dropping the $\log$.

Pop the min ::: finalize it — its distance is now true and never changes. The symbol $\infty$ means ::: "no route found yet / unreachable so far" — any finite path length beats it. A relaxation "succeeds" when ::: $dist[u]+w$ is strictly less than the current $dist[v]$ (then we lower $dist[v]$ and set $prev[v]=u$). Weight of exactly 0 ::: allowed (proof needs $\ge 0$, and $0\ge 0$). A heap entry is stale when ::: its stored distance $d$ exceeds the current $dist[u]$ (a better route was found after it was pushed). Lazy vs eager heap ::: lazy pushes a fresh pair (no decrease-key); eager lowers the existing key in place. if d > dist[u]: continue ::: skips stale lazy-heap entries. Count shortest paths: on a tie ::: add $cnt[u]$ into $cnt[v]$ instead of resetting.