2
$\begingroup$

I know that this doesn't work because shortest path with a lot of edges may have bigger weight than a longer path with less edges. But what if, you keep track of the edges that our current weight path on each node and when we compare we subtract the number of edges on this path * the constant so that we get the original weight. I understand there is also the negative cycles problem, but is there an efficient algorithm that tell if a graph contains a negative cycle ?

$\endgroup$
  • $\begingroup$ Right, I guess we could preprocessed it using Bellman-ford then perform this Dijkstra on the graph if it actually work. $\endgroup$ – Tienanh Nguyen Mar 29 '17 at 14:59
2
$\begingroup$

It's called Johnson's algorithm.

Instead of trying to keep track of the number of edges, it searches for a function $\delta:V\to \mathbb R$ so that for all edge $(v,v')$, $w(v,v')+\delta(v)-\delta(v')\ge 0$ and set that as the new weight $w'(e,e')$ of the edge $(e,e')$.

Then, for any path $p=v_1\cdot \dots\cdot v_n$ the $\delta$ values of all intermediate vertices cancel so that $w'(p)=w(p)+\delta(v_1)-\delta(v_n)$. And the shortest paths for $w$ and $w'$ therefore coincide.

Then remains the problem of finding such a $\delta$. The magic is that you can just add a new vertex $v_*$ and edges $(v_*,v)$ of weight $0$ for every vertex $v$, and then set $\delta (v)$ to be the weight of a shortest path $p_v$ from $v_*$ to $v$. Then the positiveness condition simply becomes $w(v,v')+w(p_v)-w(p_{v'})\ge 0$ which can be rewritten as $w(p_v)+w(v,v')\ge w(p_{v'})$ which is true because $p_v\cdot v'$ is a path from $v_*$ to $v'$ and $p_{v'}$ is a path from $v_*$ to $v'$ of minimal weight.

$\endgroup$
  • $\begingroup$ But does the algorithm I mentioned above correct? Since Johnson a lot more complicated, I highly doubted that the algorithm above can do the same things as Johnson with less complexity. $\endgroup$ – Tienanh Nguyen Mar 29 '17 at 18:11
  • $\begingroup$ @TienanhNguyen No. If you get the shortest path using $w'$, you may not get a shortest path for $w$ because of the length problem. And if you always keep track of the length and then use $w'(p)-|p|W$ whenever you compare, then you're just using $w$ which can have negative edges so Dijkstra may not work. $\endgroup$ – xavierm02 Mar 30 '17 at 11:04

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.