# Can Dijkstra's algorithm be modified to return paths with ascending edge-id's?

Say that each edge in a directed graph is labelled with an ID. I want to run Dijkstra on the graph to find the shortest path between $$source$$ and $$destination$$, with the additional restriction that the shortest path must be in order of ascending ID's. For example, if the path is from $$A \to B \to C$$, then $$ID(Edge_{AB}) < ID(Edge_{BC})$$.

Is this feasible in polynomial time with some modification of Dijkstra?

• What do you think? What have you tried? This site expects and encourages you to show your thoughts or partial progress toward solving the problems. People can then write answers that are more helpful for you and for future readers. – John L. Mar 7 '19 at 18:29
• Yes, there is an algorithm in polynomial time. The basic idea is to create a new graph, whose vertices are the edges of original graph. Are you still interested in an answer? – John L. Mar 12 '19 at 0:19

Basic method is to sort the path after Dijkstra applied. In this case, a compare-based algorithm will require an $$O(N \log N)$$ complexity, however in your case, you have an extra information: The edge ID's are consecutive numbers. Thus, you can use a non-comparison sorting algorithm such as counting sort with $$O(M)$$ complexity where $$M$$ is the number of edges.
2. Create an array of $$M$$ numbers initially assigned by -1.
Note that, this is an $$O(M)$$ algorithm instead of $$O(N)$$. However, if the above assumptions are satisfied, it will work better than $$O(N)$$. So, it depends on how much your graph is dense.