# Shortest path in directed graphs with no more than $\log \log n$ negative edges

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.

• 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)$. Dec 6 '21 at 9:34
• thanks ! i think its will work , and what you mean in $m$ (run time)?
– sbk
Dec 8 '21 at 12:27
• $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. Dec 8 '21 at 13:41