2
$\begingroup$

I recently faced the problem of calculating shortest paths in undirected graphs in the presence of negative edge weights; I could not find any applicable algorithms via online search.

Transforming the undirected graph to a directed one by replacing each edge $e_{ij}$ with a pair of antiparallel arcs $a_{ij}$ and $a_{ji}$ and then applying the Bellman-Ford algorithm is not an option, because egdes with negative weight correspond to a negative cycle consisting of a pair of antiparallel arcs.
Imposing the constraint, that the successor of a vertex must not be equal to its immediate predecessor doesn't rule out all negative cycles that contain a pair of antiparallel arcs, and apart from that, leaves open the question of which of the antiparallel arcs should be excluded.

After some experimenting I found this candidate transformation of a pair of antiparallel arcs (and thus for undirected edges):
Transformation preventing antiparallel edges in shortest paths

That transformation also can't rule out antiparallel arcs from appearing in a partial shortest path constructed with the Bellman-Ford algorithm; it appears to me however, that calculating the shortest path via mincost flow reliably rules out antiparallel arcs from appearing in the calculated path (in the mincost flow version the capacity of every arc is set to $1$ and the cost is set to the arc-weight and using the wellknown flow constraints for the shortest path calculation in the mincost flow formulation).


Questions:

  • have graph transformation already been described, that rule out the simultanous appearing of antiparallel arcs in the same directed cycles, i.e. that make them mutually exclusive in their appearance?

  • can the problem of ruling out antiparallel arcs in shortest paths be solved with an appropriate graph-transformation and a classical shortest path algorithm, i.e. an algorithm that is not based on mincost flow?

Improve this question
$\endgroup$
4
  • $\begingroup$ Sounds like you've already found that Johnson's algorithm does not help in your application? $\endgroup$
    – Joseph O'Rourke
    May 12, 2018 at 11:01
  • $\begingroup$ @JosephO'Rourke yes, I have also checked Johnson's algorithm and also the fact that the detection of undirected negative cost cycles is solved via T-Joins or b-matchings seems to confirm my assumption, that the classical shortest path algorithms can't deal with negative cycles of antiparallel arcs. $\endgroup$
    – Manfred Weis
    May 12, 2018 at 13:30
  • $\begingroup$ If you add the largest negative weight to all weights, so that they are all non-negative, what is the relationship between a shortest path in the modified graph to that in the original graph? $\endgroup$
    – Joseph O'Rourke
    May 12, 2018 at 15:54
  • $\begingroup$ @JosephO'Rourke adding a large weight will change the number of edges constituting to the shortest path; a path with fewer edges will penalized less than one with more edges: say you have a path with two edges of length zero and one with a single edge of length 100 - adding 1000 to each edge length makes the one with the single edge cheaper than the one with the two edges, thus obscuring the original shortest path. $\endgroup$
    – Manfred Weis
    May 12, 2018 at 16:01

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.