#18931: Boost shortest paths
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.9
Component: graph theory | Resolution:
Keywords: Boost, shortest | Merged in:
paths, Bellman-Ford, Johnson | Reviewers:
Authors: Michele Borassi | Work issues:
Report Upstream: N/A | Commit:
Branch: | fe1b51538bb57ea77793eab5f2d0a7e2800f8192
u/borassi/boost_shortest_paths | Stopgaps:
Dependencies: #18910, #18938 |
-------------------------------------+-------------------------------------
Comment (by borassi):
Hello!
Don't worry: thank you very much for having some time for me even if you
are on holidays!
See you,
Michele
Replying to [comment:8 dcoudert]:
> Hello,
>
> sorry for the late reply. Not always easy to find time when you are on
vacation ;)
>
>
> > Now I have done it! However, I still have doubts on what happens if
we run Dijkstra with negative weights. Before this patch, the result was
completely unreliable:
> >
> > {{{
> > sage: G = DiGraph([(0,1,1),(1,2,1),(0,3,1000),(3,4,-3000),
(4,2,1000)])
> > sage: G.shortest_path_length(0, 2, by_weight=True, algorithm='Bellman-
Ford_Boost')
> > -1000
> > sage: G.shortest_path_length(0, 2, by_weight=True)
> > 2
> > }}}
> > However, reading all edges to check if there are negative weights may
increase drastically the running-time, since the algorithm is sublinear.
Hence, I just added a note and two examples to show the issue. Moreover,
now, if Dijkstra algorithm finds an edge with negative weight, an error
is raised (however, if the error is not raised, it doesn't mean that the
path is correct, as shown by the previous example). Do you think it is a
good solution?
> >
>
> This is embarrassing. If the graph has a negative cycle, the `Bellman-
Ford` method should detect it!
> If you check at the method I proposed in ticket #8714 (not finalized
yet, but I can do it before or after this patch if it is interesting),
which is a much more efficient way to implement Bellman Ford, the trick
is to check that the algorithm may perform more than `n` iterations (i.e.,
a negative cost cycle allows for further reducing the costs). I don't know
how the `Bellman-Ford_Boost` method is working, but if it cannot detect
negative cost cycle, this is not good at all.
>
> We must find a way to have reliable results.
>
> Is the `Bellman-Ford_Boost` method fast? In fact, if it is not faster
than #8714, we can get ride of it and finalize #8714 instead. Let me know.
Maybe I was not clear enough when trying to explain the problem. In
particular, it comes out with *Dijkstra*, not with Bellman-Ford. The
`Bellman-Ford_Boost` algorithm is quite efficient (maybe you can improve
it with #8714, but only by constant factors), and it outputs an error if
there is a negative cycle. This error is collected by my code, and an
exception is raised, saying `ValueError: The graph contains a negative
cycle.`. So far, so good, I think.
Also Dijkstra is okay, if it is not bidirectional, as shown by the
examples of function `shortest_paths`.
The problem occurs with bidirectional Dijkstra, in routine
`shortest_path`: bidirectional algorithms are designed to cut visits as
soon as possible, so that the total running-time is sublinear. However,
these cuts are based on the fact that all unvisited edges have positive
weights. Hence, the only possibility is to hope that the user does not
ask for bidirectional algorithms with negative weights, I think. Is it
clear now?
> You could eventually add a simple example like:
> {{{
> G = 2*graphs.[wiki:PathGraph](2)
> d,_ = G.shortest_path_all_pairs()
> import itertools
> for u,v in itertools.combinations(G.vertices(),2):
> print "dist({}, {}) = {}".format(u,v, d[u].get(v,+Infinity))
> }}}
> So that non Python-expert can guess the `d[u].get(v,+Infinity)` trick.
Done!
--
Ticket URL: <http://trac.sagemath.org/ticket/18931#comment:12>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
