Given a directed graph $G=(V,E)$ with $|V|=n$ vertices and some weight function $w\colon E\to \mathbb{R}$, I also know that there are at most $\log\log n$ negative weight edges in $G$, and $G$ does not have any negative cycles.

Find minimum cost path from $s$ to $t$

My try so far:

I know that just running Bellman–Ford will be too naive, I thought generating a new $w'$ function like Johnson's algorithm does:

Something like removing any step 1 negative $e=(u,v)$ and running Dijkstra from $s$ as (single source shortest path) and $t$ (as single destination) after doing it for each edge $e$ total $\log\log n$ times, I can use shortest path as the function of $h$ like Johnson's algorithm, and it will run in $O(\log\log n \cdot n \log n)$

I'm struggling with the proof of correctness for this function $w'$, and I'm not sure if my runtime is optimal as well.

  • $\begingroup$ This negative weight edge graph construction works in your case where you create $\log \log n$ copies of the graph and then run Dijkstra's algorithm on that. Then you'll have $N = n \log \log n$ and the running time $O((N+m) \log N)$. $\endgroup$
    – Pål GD
    Dec 6, 2021 at 9:34
  • $\begingroup$ thanks ! i think its will work , and what you mean in $m$ (run time)? $\endgroup$
    – Saar BK
    Dec 8, 2021 at 12:27
  • $\begingroup$ $m$ is typically referring to the number of edges. I think you might be able to use some dynamic programming to keep it $O(m)$ for the original $m$, and not the number of edges in the created graph. $\endgroup$
    – Pål GD
    Dec 8, 2021 at 13:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.