Graphs Advanced Checkpoint

Trace fresh cases, diagnose a failed invariant, then revisit the linked explanation and implementation.

Get every question correct to pass this checkpoint. You can review feedback, revise your answers, and submit again.

1. Prerequisite edges 0→1, 1→2, 2→0 contain how many vertices in a directed cycle? Answer with the integer only.

2. Dijkstra settles a vertex under its usual proof. Which new input feature invalidates that proof?

Select one answer.

Two equal shortest paths A negative edge weight A zero-weight edge A disconnected vertex

3. Kahn topological sorting processes only 4 of 6 vertices. What does this show?

Select one answer.

The directed graph contains a cycle among the unprocessed dependencies Any returned prefix is a complete valid order All six are unreachable The graph must be undirected

4. Edges S→A weight 7, S→B weight 2, B→A weight 3 give what shortest distance from S to A? Answer with the integer only.

5. A priority queue contains distance 9 for u, but dist[u] is already 4. What should a Dijkstra loop do with the stale entry?

Select one answer.

Skip it Report a negative cycle Reset dist[u] to 9 Delete all edges from u

6. A course has two identical prerequisite pairs. Adjacency keeps both edges but indegree counts only one. What can fail?

Select one answer.

The course may become eligible before all distinct prerequisites are removed No failure is possible because duplicates are harmless in every representation The graph becomes undirected Only distance values change

Auto-advance on pass

Open access learning · Go · Python · C · SQL · No external dependencies

Transparency · Support this project

Join Discord