Hacktoberfest 2026: the issues maintainers tagged for October, open and beginner-friendly. Browse Hacktoberfest issues

Modernize BGL shortest path algorithms

Open
  • Is something wrong?
#455 1 comment 1 reaction 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
25/100
Issue type
Feature
Clarity
Mostly clear
Activity status
Stale
Tech stack
cpp

Research direction

Start by reviewing the Boost Graph shortest-path algorithms named in the issue and the cited papers for the proposed alternatives. The issue does not identify files, tests, or a single algorithm to implement; first determine a bounded algorithm and integration scope with maintainers. Done would require implementing and testing the agreed algorithm, but that scope is not yet specified.

Written by the indexing model from the issue text.

Description

algorithm

The Sage Math graph module 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, 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, cited ~13x) : best speed/memory tradeoff for finding k alternative paths, most performant
  • k-Shortest Simple Paths, SB* variant, (Al Zoobi et al 2023, cited ~13x) : fastest for small k, higher memory
  • Contraction Hierarchies (Geisberger et al., 2008, cited ~1200x) : amazing for road networks, 1000x+ speedup over Dijkstra
  • Hub labelling ( Abraham et al., 2011, cited ~400x) : sub-milliseconds shorttest path length oracle: avoids running dijsktra millions of times
Dominant language
C++
Stars
396
Forks
244
Avg merge
2d 6h
Merged PRs (30d)
29

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from boostorg/graph

All issues in boostorg/graph

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.