Modernize BGL shortest path algorithms
- Lenguaje dominante
- C++
- Estrellas
- 392
- Forks
- 239
- Merge medio
- 1 d 11 min
- PR fusionados (30 d)
- 20
Descripción
The [Sage Math graph module](https://doc.sagemath.org/html/en/reference/graphs/index.html) uses Boost Graph. This quick exploration comes from kind feedback from its maintainer David Coudert:
The BGL currently implements traditional (~1990) algorithms for shortest paths:
- `dijkstra_shortest_paths` : 1959 single source, single shortest path tree, but constrained to positive weights
- `bellman_ford_shortest_paths` : 1958 extends to negative weights with negative cycle detection
- `johnson_all_pairs_shortest_paths` : 1977 combines bellman for reweighting with dijkstra running for each vertex
- `floyd_warshall_all_pairs_shortest_paths` : 1962 better than johnson for dense graphs, uses dynamic programming
- `astar_search`: 1968 single source to single target path, heuristically
But it lacks more modern algorithms:
- Yen's algorithm ([Yen 1971](https://web.archive.org/web/20180724053349id_/http://www.ams.org/journals/qam/1970-27-04/S0033-569X-1970-0253822-7/S0033-569X-1970-0253822-7.pdf), cited ~500x) : k-shortest simple (loopless) paths between two vertices. At each iteration, finds the next shortest path by deviating from previously found paths. Baseline must-have
- k-Shortest Simple Paths, Postponed Node Classification algorithm variant, ([Al Zoobi et al 2023](https://dl.acm.org/doi/pdf/10.1145/3626567), cited ~13x) : best speed/memory tradeoff for finding k alternative paths, most performant
- k-Shortest Simple Paths, SB* variant, ([Al Zoobi et al 2023](https://dl.acm.org/doi/pdf/10.1145/3626567), cited ~13x) : fastest for small k, higher memory
- Contraction Hierarchies ([Geisberger et al., 2008](https://ae.iti.kit.edu/download/diploma_thesis_geisberger.pdf), cited ~1200x) : amazing for road networks, 1000x+ speedup over Dijkstra
- Hub labelling ( [Abraham et al., 2011](https://www.microsoft.com/en-us/research/wp-content/uploads/2010/12/HL-TR.pdf), cited ~400x) : sub-milliseconds shorttest path length oracle: avoids running dijsktra millions of times
Guía de contribución
Evaluación
Este issue todavía no se ha evaluado.