Run Dijkstra’s algorithm on the following graph. How many times does each vertex’s key decrease? Recall that D [ v ] is the key of vertex v v ; it represents the algorithm’s current best‑known estimate of the shortest‑path distance from the source s to v v . (Decrease from infinity counts as decrease) The a decreases [Fill in the blank] times. The b decreases [Fill in the blank] times. The c decreases [Fill in the blank] times. The d decreases [Fill in the blank] times

Dijkstra’s relaxation updates (decreases) occur whenever we find a strictly smaller tentative distance. Use these directed edges and weights read from the diagram: s->a = 2, s->b = 9, a->c = 2, a->d = 20, c->b = 1, c->d = 8, b->d = 2. Initial keys: d[s]=0, d[a]=d[b]=d[c]=d[d]=∞. 1) Relax edges out of s: - relax s->a: d[a] becomes 2 (∞ -> 2). Count: a: 1. - relax s->b: d[b] becomes 9 (∞ -> 9). Count: b: 1. Current keys: a=2, b=9, c=∞, d=∞. 2) Extract minimum: a (key 2). Relax edges from a: - relax a->c: d[c] becomes 2 + 2 = 4 (∞ -> 4). Count: c: 1. - relax a->d: d[d] becomes 2 + 20 = 22 (∞ -> 22). Count: d: 1. Current keys: c=4, b=9, d=22. 3) Extract minimum: c (key 4). Relax edges from c: - relax c->b: d[b] becomes 4 + 1 = 5 (9 -> 5). This is a decrease for b. Count: b: 2. - relax c->d: d[d] becomes 4 + 8 = 12 (22 -> 12). This is a decrease for d. Count: d: 2. Current keys: b=5, d=12. 4) Extract minimum: b (key 5). Relax edges from b: - relax b->d: d[d] becomes 5 + 2 = 7 (12 -> 7). This is another decrease for d. Count: d: 3. No other relaxations improve keys. 5) Extract d (key 7). No further improvements. Summary of decreases: - a: decreased once (∞ -> 2). - b: decreased twice (∞ -> 9, then 9 -> 5). - c: decreased once (∞ -> 4). - d: decreased three times (∞ -> 22, 22 -> 12, 12 -> 7). Why other counts are wrong: any smaller count for b would ignore the update via c (4+1=5); any smaller count for d would ignore successive improvements via a then c then b. These stepwise relaxations yield exactly the counts above. Final answer confirmed: a = 1, b = 2, c = 1, d = 3.