4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Undirected graph can be converted to directed graphs ny replacing a undirected edge with 2 directed edges in different direction. $\endgroup$
    – Tushar
    Commented May 15, 2014 at 20:01
  • $\begingroup$ Just a note, Dijkstra's algorithm works for graphs that can have negative edges. It only fails if the graph has negative weight cycles. EDIT: Just realized that a negative edge means a negative cycle for undirected graphs. $\endgroup$
    – Tushar
    Commented May 15, 2014 at 20:02
  • 2
    $\begingroup$ @Tushar Nope. Dijkstra will fail for negative edges. Starting in a, with edges (a,3,b), (a,5,c), and (c,-3,b) Dijkstra will claim the distance to b equals 3 in the first step, only to discover later it is 2 via node c. No negative edges. $\endgroup$
    – Hendrik Jan
    Commented May 16, 2014 at 23:38
  • $\begingroup$ cs.stackexchange.com/q/23938/755 $\endgroup$
    – D.W. ♦
    Commented Mar 23, 2023 at 18:50

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The defect of replacing an edge $\{\,u, v\,\}$ of negative weight by two arcs $(u, v)$ and $(v, u)$ is that you produce a cycle $v, (v, u), u, (u, v), v$ of negative weight. $\endgroup$
    – Smylic
    Commented Jun 3, 2015 at 22:55
1
$\begingroup$

After making the graph undirected, you can use Johnson's Algorithm, which works by using the Bellman–Ford algorithm to modify the input graph removing all negative weights, allowing Dijkstra's algorithm to be used on the resultant graph. It has a time complexity of $O(V^2 \log V + VE)$, which is better than Floyd-Warshall alone!

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.