Graphs Advanced: Dependency Order and Weighted Paths

You will implement CanFinish, FindOrder and DijkstraShortestPath. Prepare by constructing an adjacency list and using a queue and min-heap. The first question is what an edge means: a prerequisite is an ordering constraint, while a weighted edge is a possible travel cost. Their frontiers certify different facts.

Translate prerequisites before traversing

A pair [a,b] means take b before a, so the graph edge is b -> a. indegree[a] counts unmet incoming prerequisites. Kahn's algorithm starts with all zero-indegree courses, including isolated courses. Removing a course removes its outgoing constraints; enqueue a neighbor only when its remaining count becomes zero.

For 5 courses and pairs [[2,0],[2,1],[3,2]]:

Removed course	Remaining indegrees [0,1,2,3,4]	Queue after removal
none	[0,0,2,1,0]	[0,1,4]
0	[0,0,1,1,0]	[1,4]
1	[0,0,0,1,0]	[4,2]
4	[0,0,0,1,0]	[2]
2	[0,0,0,0,0]	[3]
3	[0,0,0,0,0]	[]

One order is [0,1,4,2,3]. There may be many; tests should check every edge points forward and every course appears once, rather than compare with a single chosen order. Duplicate prerequisite pairs are safe if both adjacency and indegree count them consistently. Deduplicating only one side breaks the count.

A stuck frontier is evidence of a cycle

If courses remain but none has indegree zero, every remaining node has an incoming edge from another remaining node. Follow those incoming edges in a finite graph: some node repeats, exhibiting a directed cycle. Conversely a cycle can never release its first node, because that node still depends on another cycle member. Thus processing all n nodes is equivalent to feasibility.

For pairs [[1,0],[2,1],[1,2]] and isolated course 3, the initial queue is [0,3]. Removing those two leaves courses 1 and 2 waiting on each other. Returning “true because the queue initially had a node” is wrong. CanFinish returns false; FindOrder returns an empty list, not the partial prefix. Building and processing the graph takes O(V+E) time and space.

Dijkstra pops a distance claim, not just a node

The task's directed edges are [u,v,w] with positive integer weights. Dijkstra's proof also permits zero weights, but negative weights invalidate its settling argument. Initialize source distance to 0 and other distances to an unreachable marker. Push (0,src) into a min-heap ordered by distance.

Trace nodes 0..4 with edges 0->1:8, 0->2:2, 2->1:1, 2->3:7, 1->3:2:

Popped (distance,node)	Action	Best distances
(0,0)	Relax 1 and 2	[0,8,2,∞,∞]
(2,2)	Improve 1 to 3, discover 3 at 9	[0,3,2,9,∞]
(3,1)	Improve 3 to 5	[0,3,2,5,∞]
(5,3)	No outgoing improvements	[0,3,2,5,∞]
(8,1)	Stale: 8 differs from best[1]=3; skip	unchanged
(9,3)	Stale: 9 differs from best[3]=5; skip	unchanged

Return [0,3,2,5,-1]; node 4 remains unreachable. A node's first discovery is not final: node 1 is first seen with 8 but later improved to 3. Marking it visited on insertion would reject that improvement. In a heap without decrease key, push the new claim and leave the old entry to be discarded on extraction.

Why is a nonstale minimum claim final? Any alternative route to it must first cross from settled to unsettled nodes. The crossing prefix cannot cost less than the smallest current frontier distance; adding nonnegative edges cannot make it smaller later. This is the exchange-like step that a FIFO queue lacks when edge weights differ. BFS minimizes edge count, which only matches cost when all edges have the same cost.

Representation and work bounds are part of the contract

Never relax from an infinity value, and choose infinity larger than every valid finite distance. Under the exercise bounds, a shortest simple path uses at most n-1 edges of weight at most 10^6: below 10^11. Go's current reference uses 64-bit int and a 1<<60 sentinel; its API and maximum domain do not fit a 32-bit target. Return -1 only for unreachable nodes, including after converting from the internal marker.

A lazy binary heap can hold O(E) distance claims, not only O(V). Its total bound is O(V+E log(E+1)) time and O(V+E) space including adjacency. An indexed heap with decrease-key has a different bound and storage model. Do not claim that stale entries are impossible merely because a vertex is settled once. Princeton's shortest-path treatment explains the nonnegative-edge condition and the priority-queue variants.

Reconstruct with a changed graph

1. For pairs [[1,0],[2,0],[3,1],[3,2]], after removing 0 then 1, is course 3 eligible? Finish a valid order and identify the remaining prerequisite.
2. Add a cycle 3->2 to the worked dependency graph. Which courses can still be emitted, and why must FindOrder discard that partial output?
3. For edges 0->1:9, 0->2:4, 2->1:2, 1->3:1, give final distances and the heap claim that becomes stale. Then make 2->1 weight -8 and explain why the nonnegative-edge proof can no longer be cited, even if this particular traversal happens to find the right answer.

Check your reconstruction

1. No: 3 still depends on 2. [0,1,2,3] is valid.
2. Courses 0, 1 and isolated 4 can be emitted, but 2 and 3 wait on each other. A partial prefix is not an order completing all courses.
3. [0,6,4,7]; (9,1) becomes stale. A negative edge can make an as-yet unprocessed prefix lead to a smaller final distance; extending a path is no longer monotone in cost. The algorithmic guarantee, not one sample, fails.

Implement the three tasks. Test disconnected graphs, self-cycles, duplicate prerequisites, multiple valid orders and repeated improvements. Independently check small weighted graphs with repeated full edge relaxation. Later, explain why a queue entry in Kahn certifies eligibility, whereas a nonstale heap pop in Dijkstra certifies minimum distance.