8000 [BTS-1636] Fix path found by SHORTEST_PATH with weight is not path of… · trooso/arangodb@0a9f667 · GitHub 8000
[go: up one dir, main page]
Skip to content

Commit 0a9f667

Browse files
markuspfmarkuspf
authored
[BTS-1636] Fix path found by SHORTEST_PATH with weight is not path of lowest weight (arangodb#20305)
When searching for (in particular weighted) shortest paths, ArangoDB searches forward from the start and backward from the target vertex with something that looks quite a lot like a Dijkstra search. An important aspect is when a search is finished, that is when a lowest weight path has been found. Whenever a vertex is relaxed, every newly discovered vertex is checked whether it has been seen on the other side of the search. If it has been a path has been found, but there is no guarantee that this is the lowest weight one. The search has to continue until the sum of the diameters, the weight of the highest proven weight paths, exceeds the weight of the best candidate found. This patch implements this terminating condition. In addition, since the two sided enumerator supports enumerating all paths between two vertices in increasing order by weight, by extension all weights below the sum of the diameters threshold are deemed to be optimal and hence all paths with weight below the threshold can be returned.
1 parent 788adec commit 0a9f667

File tree

9 files changed

+4182
-156
lines changed

9 files changed

+4182
-156
lines changed

‎CHANGELOG

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,9 @@
11
devel
22
-----
33

4+
* Fix BTS-1636: Under certain circumstances the path found by a weighted
5+
shortest path search was not the path of smallest weight.
6+
47
* Added CMake option `USE_JEMALLOC_CHECKS` to toggle the usage of extra safety
58
checks in jemalloc. The option is currently enabled by default, but can be
69
turned off when there are performance concerns.

0 commit comments

Comments
 (0)
0