I've been trying to solve this problem.
Here's my approach: I used Dijkstra, where W(u, v) is the minimum number of orders required to get from the starting vertex to v. To find out if I needed an order at a vertex, I maintained a set of "available" vertices from a given vertex (i.e. outdegree), removing a vertex once it's explored.
Here's my solution.
All help is appreciated!