CODEWITHSUNDEEP
algorithmgraph
devsda
devsda

Reputation: 4232

Minimum edges to remove to reach destination

I faced one competition, where I got stuck in one question. Please help me in this.

  1. Directed Graph is given.
  2. Nodes indexes as 0, 1, 2, ..., N.

Starting point - 0. Ending Point - N.

Contraints :-

If we are at node i, and that node has numbers of children, then we can only move to smallest index node from node i.

Tell me the minimum numbers of edges that I have to delete to reach from 0 to N.

I am totally stuck in this. Please answer.

Upvotes: 0

Views: 69

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

Set the cost of each arc to the number of arcs with the same tail whose head has a smaller index. Run your favorite shortest path algorithm.

Upvotes: 3

Related Questions