graph/path: Improve performance of YenKShortestPaths
#2004
Conversation
This variant can terminate early when the target is reached. This can make a large difference in running time for Yen's k-shortest paths algorithm, as it makes many calls to the shortest path subroutine.
BarrensZeppelin
force-pushed
the
graph/spsp
branch
from
1ed9bd6 to
c736b6a
Compare
|
Done. See #2005 |
|
It does not have the same effect.
With the implementation in the PR, only nodes 1, 2 and 4 are pushed to the priority queue, and only nodes 1 and 2 are popped. I guess it's possible to achieve the same effect with composition by making the |
This comment was marked as outdated.
This comment was marked as outdated.
|
No, you're right. |
graph/path/dijkstra.go
Outdated
| // has a u-reachable negative edge weight that is discovered before reaching v. | ||
| // | ||
| // The time complexity of DijkstraFromTo is O(|E|.log|V|). | ||
| func DijkstraFromTo(u graph.Node, v graph.Node, g traverse.Graph) (path []graph.Node, weight float64) { |
There was a problem hiding this comment.
| func DijkstraFromTo(u graph.Node, v graph.Node, g traverse.Graph) (path []graph.Node, weight float64) { | |
| func DijkstraFromTo(u, t graph.Node, g traverse.Graph) (path []graph.Node, weight float64) { |
The second param is not a v.
graph/path/dijkstra.go
Outdated
| // Shared implementation of DijkstraFrom and DijkstraFromTo. | ||
| func dijkstraFrom(u, target graph.Node, g traverse.Graph) Shortest { |
There was a problem hiding this comment.
| // Shared implementation of DijkstraFrom and DijkstraFromTo. | |
| func dijkstraFrom(u, target graph.Node, g traverse.Graph) Shortest { | |
| func dijkstraFrom(u, t graph.Node, g traverse.Graph) Shortest { |
graph/path/dijkstra_test.go
Outdated
|
|
||
| np, weight := pt.To(test.NoPathFor.To().ID()) | ||
| if pt.From().ID() == test.NoPathFor.From().ID() && (np != nil || !math.IsInf(weight, 1)) { | ||
| t.Errorf("%q %s: unexpected path:\ngot: path=%v weight=%f\nwant:path=<nil> weight=+Inf", | ||
| test.Name, tg.typ, np, weight) | ||
| } | ||
| } | ||
|
|
There was a problem hiding this comment.
I think this should be in the loop, with helper sharing.
Also rename `v` parameter to `t`.
BarrensZeppelin
force-pushed
the
graph/spsp
branch
from
c736b6a to
f112007
Compare
YenKShortestPaths's running time is dominated by calls to Dijkstra's shortest path algorithm, so it makes sense to focus on improvements there.For Yen's algorithm, we are not interested in shortest path trees, but only a shortest path between some source and target node. We can exploit this in Dijkstra's algorithm by terminating when the target is discovered.
Of course this does not improve the worst-case complexity, but it should be a worthwhile optimization for many practical uses.