Shortest path in weighted(positive or negative) undirected graph

Problem Detail: 

I have to find an algorithm that finds the SSSP (single-source shortest path - shortest paths from one source vertex to all other vertices) on a weighted undirected graph. If there are 2 different shortest paths, the algorithm should prefer the one with less edges on it. The time complexity of the algorithm is $O((|V|+|E|) \log |V|)$.

So, I tried:

• My first thought was DFS/BFS (the $O(|V|+|E|)$ looks tempting), but (I believe) no modification of these two algorithms works on weighed graphs.
• Then I thought about Dijkstra's algorithm - but that one doesn't work on graphs, which can have negative edges.
• My last hope was Bellman-Ford algorithm, which could work I guess, but I have no idea, how to rewrite it for undirected graphs.

Any hint is appreciated.

Asked By : Wanderer

Answered By : Sayan Bandyapadhyay

A generic scheme to make an undirected graph directed is to replace each of its edges by two directed edges with same weight as the original weight of the edge. For an undirected edge $(u,v)$. Replace it by two directed edges $(u,v)$(direction u to v) and $(v,u)$(direction v to u). The weight of both of these edges are same as weight of undirected edge $(u,v)$.

Thus the algorithm which you have in mind for solving directed SSSP can also be applied on undirected graph with the above mentioned changes.

And, a good way to get a shortest path with smallest number of edges is to add a small constant weight ($\epsilon$) to all edges. Note that if we have two shortest path having $x$ and $y$ edges ($x > y$) before, then adding small value to all edges changes the weight of the shortest path with $x$ and $y$ edges by amount $x\epsilon$ and $y\epsilon$. As $x\epsilon > y\epsilon$, now the shortest path with $y$ edges is having lesser cost. Thus after changing the edge weight by a very small amount you can apply your favorite SSSP algo to get the path with minimum number of edges. Note that as $\epsilon$ is very small a path which was not shortest before can't be shortest after changing the weights.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24768