0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Apass.Jack Mar 7 at 18:29
  • 2
    $\begingroup$ 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? $\endgroup$ – Apass.Jack Mar 12 at 0:19
1
$\begingroup$

It is possible assuming that your edge ID's are consecutive numbers (usually that's the case) and the graph is not dense, however, it will require extra amount of memory.

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.

The method:

  1. Apply usual Dijkstra on the problem and find the shortest path.
  2. Create an array of $M$ numbers initially assigned by -1.
  3. As traversing the shortest path, change the value of each traversed edge ID position in the array to 1.
  4. Scan the array for 1's to find the path in ascending order.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.