JuliaGraphs / JuliaGraphs/Graphs.jl

[BUG] `enumerate_paths` does not give all paths

Open
#478 7 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug
Dominant language
Julia
Stars
538
Forks
128
Avg merge
10h 25m
Merged PRs (30d)
2

Description

the function enumerate_paths, when passed a DijkstraState, does not enumerate all paths as advertised.

below, I create a minimal example.

	# construct graph
	my_g = SimpleGraph(5)
	add_edge!(my_g, 1, 2)
	add_edge!(my_g, 3, 2)
	add_edge!(my_g, 2, 4)
	add_edge!(my_g, 3, 4)
	add_edge!(my_g, 5, 4)
	add_edge!(my_g, 5, 3)

	# find all shortest paths from node 5 to other nodes
	my_dsp = dijkstra_shortest_paths(my_g, 5, allpaths=true)

	# enumerate paths from node 5 to 1
	print(enumerate_paths(my_dsp, 1)) # only gives one path!

	graphplot(my_g, nlabels=["$i" for i = 1:5])

Expected behavior
I expect enumerate_paths(my_dsp, 1) to give both:


[5, 3, 2, 1]

[5, 4, 2, 1]
Image

but it only gives one of the paths.

Version information

Julia Version 1.12.2
Commit ca9b6662be4 (2025-11-20 16:25 UTC)
Build Info:
  Official https://julialang.org release
Platform Info:
  OS: macOS (arm64-apple-darwin24.0.0)
  CPU: 8 × Apple M3
  WORD_SIZE: 64
  LLVM: libLLVM-18.1.7 (ORCJIT, apple-m3)
  GC: Built with stock GC
Threads: 1 default, 1 interactive, 1 GC (on 4 virtual cores)

Status ~/.julia/environments/v1.12/Project.toml
[86223c79] Graphs v1.13.2


Contributor guide

Open the contributing guide

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.

Research direction

Start with enumerate_paths and the DijkstraState produced by dijkstra_shortest_paths(..., allpaths=true), then reproduce the minimal five-node graph from the issue. Trace why enumerate_paths(my_dsp, 1) returns only one route; done means it returns both expected shortest paths, with the existing behavior verified against this example.

Written by the indexing model from the issue text.

Assessment

Tech stack
julia
Domain
data
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
72/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.