In my economics research I am currently dealing with a specific shortest path problem:

Given a directed deterministic dynamic graph with weights on the edges, I need to find the shortest path from one source $S$, which goes through $N$ edges. The graph can have cycles, the edge weights could be negative, and the path is allowed to go through a vertex or edge more than once.

Is there an efficient algorithm for this problem?

| cite | improve this question | | | | |
  • 1
    $\begingroup$ In order to handle the edge constraint, form a directed layered graph with $N+1$ layers. Each edge $(i,j)$ in the original graph corresponds to $N$ edges $i \to j$ from the $r$'th layer to the $(r+1)$'th layer. Now look for a shortest path from the copy in the first later to the copy in the last layer. $\endgroup$ – Yuval Filmus Jun 28 '18 at 15:32
  • $\begingroup$ To illustrate the idea : all vertices are a "state" of the economy. And two vertices are linked by an edge if there exists a "decision" which allows the economy to jump from one state to an other at every time step. Therefore, you can stay on the same state (the same vertex) by "doing nothing" as a decision. Each decision has a "cost" that evolves in time which is modeled by dynamic weights on the edges. And I am looking to the paths through which the economy can go after N decisions (therefore N time steps as there is one decision per time step) and therefore N edges. $\endgroup$ – AlexC75 Jun 28 '18 at 15:47
  • $\begingroup$ So yes I forgot to mention that it is a deterministic dynamic oriented graph. Sorry. $\endgroup$ – AlexC75 Jun 28 '18 at 15:47
  • $\begingroup$ Please don't leave clarifications in the comments. Instead, edit the question to make it clear and read well for someone who encounters the question for the first time. I've done the edit for you this time, but in the future please respond to requests for clarification by editing the post rather than leaving a comment. $\endgroup$ – D.W. Jun 29 '18 at 0:03
  • $\begingroup$ @YuvalFilmus thank you for your comment, I really appreciate. Could you explain me what you mean by : "Each edge (i,j) in the original graph corresponds to N edges i→j from the r'th layer to the (r+1)'th layer." $\endgroup$ – AlexC75 Jun 29 '18 at 9:50