diff --git a/graph/path/bellman_ford_moore_test.go b/graph/path/bellman_ford_moore_test.go
index 237d702..f5835ca 100644
--- a/graph/path/bellman_ford_moore_test.go
+++ b/graph/path/bellman_ford_moore_test.go
@@ -170,6 +170,37 @@
 				}
 			}
 
+			paths = paths[:0]
+			pt.AllToFunc(test.Query.To().ID(), func(path []graph.Node) {
+				paths = append(paths, append([]graph.Node(nil), path...))
+			})
+			if weight := pt.WeightTo(test.Query.To().ID()); !math.IsInf(test.Weight, -1) && weight != test.Weight {
+				t.Errorf("%q %s: unexpected weight from Weight: got:%f want:%f",
+					test.Name, tg.typ, weight, test.Weight)
+			}
+
+			gotPaths = nil
+			if len(paths) != 0 {
+				gotPaths = make([][]int64, len(paths))
+			}
+			for i, p := range paths {
+				for _, v := range p {
+					gotPaths[i] = append(gotPaths[i], v.ID())
+				}
+			}
+			if test.HasNegativeCycleInPath {
+				if gotPaths != nil {
+					t.Errorf("testing %q %s: unexpected shortest paths:\ngot: %v\nwant: []",
+						test.Name, tg.typ, gotPaths)
+				}
+			} else {
+				ordered.BySliceValues(gotPaths)
+				if !reflect.DeepEqual(gotPaths, test.WantPaths) {
+					t.Errorf("testing %q %s: unexpected shortest paths:\ngot: %v\nwant:%v",
+						test.Name, tg.typ, gotPaths, test.WantPaths)
+				}
+			}
+
 			// Test absent paths.
 			np, weight, unique := pt.To(test.NoPathFor.To().ID())
 			if pt.From().ID() == test.NoPathFor.From().ID() && !(np == nil && math.IsInf(weight, 1) && !unique) {
diff --git a/graph/path/dijkstra_test.go b/graph/path/dijkstra_test.go
index ca9d953..45deec2 100644
--- a/graph/path/dijkstra_test.go
+++ b/graph/path/dijkstra_test.go
@@ -188,6 +188,34 @@
 					test.Name, gotPaths, test.WantPaths)
 			}
 
+			paths = paths[:0]
+			pt.AllToFunc(test.Query.To().ID(), func(path []graph.Node) {
+				paths = append(paths, append([]graph.Node(nil), path...))
+			})
+			if weight != test.Weight {
+				t.Errorf("%q %s: unexpected weight from AllTo: got:%f want:%f",
+					test.Name, tg.typ, weight, test.Weight)
+			}
+			if weight := pt.WeightTo(test.Query.To().ID()); !math.IsInf(test.Weight, -1) && weight != test.Weight {
+				t.Errorf("%q %s: unexpected weight from Weight: got:%f want:%f",
+					test.Name, tg.typ, weight, test.Weight)
+			}
+
+			gotPaths = nil
+			if len(paths) != 0 {
+				gotPaths = make([][]int64, len(paths))
+			}
+			for i, p := range paths {
+				for _, v := range p {
+					gotPaths[i] = append(gotPaths[i], v.ID())
+				}
+			}
+			ordered.BySliceValues(gotPaths)
+			if !reflect.DeepEqual(gotPaths, test.WantPaths) {
+				t.Errorf("testing %q %s: unexpected shortest paths:\ngot: %v\nwant:%v",
+					test.Name, tg.typ, gotPaths, test.WantPaths)
+			}
+
 			// Test absent paths.
 			np, weight, unique := pt.To(test.NoPathFor.To().ID())
 			if pt.From().ID() == test.NoPathFor.From().ID() && !(np == nil && math.IsInf(weight, 1) && !unique) {
@@ -296,6 +324,25 @@
 				test.Name, got, test.WantPaths)
 		}
 
+		paths = paths[:0]
+		pt.AllBetweenFunc(test.Query.From().ID(), test.Query.To().ID(), func(path []graph.Node) {
+			paths = append(paths, append([]graph.Node(nil), path...))
+		})
+		got = nil
+		if len(paths) != 0 {
+			got = make([][]int64, len(paths))
+		}
+		for i, p := range paths {
+			for _, v := range p {
+				got[i] = append(got[i], v.ID())
+			}
+		}
+		ordered.BySliceValues(got)
+		if !reflect.DeepEqual(got, test.WantPaths) {
+			t.Errorf("testing %q: unexpected shortest paths:\ngot: %v\nwant:%v",
+				test.Name, got, test.WantPaths)
+		}
+
 		nps, weight := pt.AllBetween(test.NoPathFor.From().ID(), test.NoPathFor.To().ID())
 		if nps != nil || !math.IsInf(weight, 1) {
 			t.Errorf("%q: unexpected path:\ngot: paths=%v weight=%f\nwant:path=<nil> weight=+Inf",
diff --git a/graph/path/floydwarshall_test.go b/graph/path/floydwarshall_test.go
index 800c067..15afff3 100644
--- a/graph/path/floydwarshall_test.go
+++ b/graph/path/floydwarshall_test.go
@@ -93,6 +93,25 @@
 				test.Name, got, test.WantPaths)
 		}
 
+		paths = paths[:0]
+		pt.AllBetweenFunc(test.Query.From().ID(), test.Query.To().ID(), func(path []graph.Node) {
+			paths = append(paths, append([]graph.Node(nil), path...))
+		})
+		got = nil
+		if len(paths) != 0 {
+			got = make([][]int64, len(paths))
+		}
+		for i, p := range paths {
+			for _, v := range p {
+				got[i] = append(got[i], v.ID())
+			}
+		}
+		ordered.BySliceValues(got)
+		if !reflect.DeepEqual(got, test.WantPaths) {
+			t.Errorf("testing %q: unexpected shortest paths:\ngot: %v\nwant:%v",
+				test.Name, got, test.WantPaths)
+		}
+
 		nps, weight := pt.AllBetween(test.NoPathFor.From().ID(), test.NoPathFor.To().ID())
 		if nps != nil || !math.IsInf(weight, 1) {
 			t.Errorf("%q: unexpected path:\ngot: paths=%v weight=%f\nwant:path=<nil> weight=+Inf",
diff --git a/graph/path/johnson_apsp_test.go b/graph/path/johnson_apsp_test.go
index d522ff9..c796f20 100644
--- a/graph/path/johnson_apsp_test.go
+++ b/graph/path/johnson_apsp_test.go
@@ -93,6 +93,25 @@
 				test.Name, got, test.WantPaths)
 		}
 
+		paths = paths[:0]
+		pt.AllBetweenFunc(test.Query.From().ID(), test.Query.To().ID(), func(path []graph.Node) {
+			paths = append(paths, append([]graph.Node(nil), path...))
+		})
+		got = nil
+		if len(paths) != 0 {
+			got = make([][]int64, len(paths))
+		}
+		for i, p := range paths {
+			for _, v := range p {
+				got[i] = append(got[i], v.ID())
+			}
+		}
+		ordered.BySliceValues(got)
+		if !reflect.DeepEqual(got, test.WantPaths) {
+			t.Errorf("testing %q: unexpected shortest paths:\ngot: %v\nwant:%v",
+				test.Name, got, test.WantPaths)
+		}
+
 		nps, weight := pt.AllBetween(test.NoPathFor.From().ID(), test.NoPathFor.To().ID())
 		if nps != nil || !math.IsInf(weight, 1) {
 			t.Errorf("%q: unexpected path:\ngot: paths=%v weight=%f\nwant:path=<nil> weight=+Inf",
diff --git a/graph/path/shortest.go b/graph/path/shortest.go
index db6bb03..4fcd239 100644
--- a/graph/path/shortest.go
+++ b/graph/path/shortest.go
@@ -420,38 +420,67 @@
 	}
 
 	seen := make([]bool, len(p.nodes))
-	paths = p.allTo(from, to, seen, []graph.Node{p.nodes[to]}, nil)
+	p.allTo(from, to, seen, []graph.Node{p.nodes[to]}, func(path []graph.Node) {
+		paths = append(paths, append([]graph.Node(nil), path...))
+	})
 	weight = p.dist[to]
 
 	return paths, weight
 }
 
+// AllToFunc calls fn on all shortest paths to v. Paths containing zero-weight
+// cycles are not considered. If a negative cycle exists between u and v, no
+// path is considered. The fn closure must not retain the path parameter.
+func (p ShortestAlts) AllToFunc(vid int64, fn func(path []graph.Node)) {
+	from := p.indexOf[p.from.ID()]
+	to, toOK := p.indexOf[vid]
+	if !toOK || len(p.next[to]) == 0 {
+		if p.from.ID() == vid {
+			fn([]graph.Node{p.nodes[from]})
+		}
+		return
+	}
+
+	_, weight, unique := p.To(vid)
+	if math.IsInf(weight, -1) && !unique {
+		return
+	}
+
+	seen := make([]bool, len(p.nodes))
+	p.allTo(from, to, seen, []graph.Node{p.nodes[to]}, fn)
+}
+
 // allTo recursively constructs a slice of paths extending from the node
 // indexed into p.nodes by from to the node indexed by to. len(seen) must match
 // the number of nodes held by the receiver. The path parameter is the current
-// working path and the results are written into paths.
-func (p ShortestAlts) allTo(from, to int, seen []bool, path []graph.Node, paths [][]graph.Node) [][]graph.Node {
+// working path and the results passed to fn.
+func (p ShortestAlts) allTo(from, to int, seen []bool, path []graph.Node, fn func(path []graph.Node)) {
 	seen[to] = true
 	if from == to {
 		if path == nil {
-			return paths
+			return
 		}
 		ordered.Reverse(path)
-		return append(paths, path)
+		fn(path)
+		ordered.Reverse(path)
+		return
 	}
 	first := true
+	var seenWork []bool
 	for _, to := range p.next[to] {
 		if seen[to] {
 			continue
 		}
 		if first {
-			path = append([]graph.Node(nil), path...)
+			p := make([]graph.Node, len(path), len(path)+1)
+			copy(p, path)
+			path = p
+			seenWork = make([]bool, len(seen))
 			first = false
 		}
-		path = path[:len(path):len(path)]
-		paths = p.allTo(from, to, append([]bool(nil), seen...), append(path, p.nodes[to]), paths)
+		copy(seenWork, seen)
+		p.allTo(from, to, seenWork, append(path, p.nodes[to]), fn)
 	}
-	return paths
 }
 
 // negEdge is a key into the negative costs map used by Shortest and ShortestAlts.
@@ -681,16 +710,51 @@
 		n = p.nodes[to]
 	}
 	seen := make([]bool, len(p.nodes))
-	paths = p.allBetween(from, to, seen, []graph.Node{n}, nil)
+	p.allBetween(from, to, seen, []graph.Node{n}, func(path []graph.Node) {
+		paths = append(paths, append([]graph.Node(nil), path...))
+	})
 
 	return paths, weight
 }
 
-// allBetween recursively constructs a slice of paths extending from the node
+// AllBetweenFunc calls fn on all shortest paths from u to v. Paths containing
+// zero-weight cycles are not considered. If a negative cycle exists between u
+// and v, no path is considered. The fn closure must not retain the path
+// parameter.
+func (p AllShortest) AllBetweenFunc(uid, vid int64, fn func(path []graph.Node)) {
+	from, fromOK := p.indexOf[uid]
+	to, toOK := p.indexOf[vid]
+	if !fromOK || !toOK || len(p.at(from, to)) == 0 {
+		if uid == vid {
+			if !fromOK {
+				fn([]graph.Node{node(uid)})
+				return
+			}
+			fn([]graph.Node{p.nodes[from]})
+			return
+		}
+		return
+	}
+
+	if math.Float64bits(p.dist.At(from, to)) == defacedBits {
+		return
+	}
+
+	var n graph.Node
+	if p.forward {
+		n = p.nodes[from]
+	} else {
+		n = p.nodes[to]
+	}
+	seen := make([]bool, len(p.nodes))
+	p.allBetween(from, to, seen, []graph.Node{n}, fn)
+}
+
+// allBetween recursively constructs a set of paths extending from the node
 // indexed into p.nodes by from to the node indexed by to. len(seen) must match
 // the number of nodes held by the receiver. The path parameter is the current
-// working path and the results are written into paths.
-func (p AllShortest) allBetween(from, to int, seen []bool, path []graph.Node, paths [][]graph.Node) [][]graph.Node {
+// working path and the results passed to fn.
+func (p AllShortest) allBetween(from, to int, seen []bool, path []graph.Node, fn func([]graph.Node)) {
 	if p.forward {
 		seen[from] = true
 	} else {
@@ -698,20 +762,28 @@
 	}
 	if from == to {
 		if path == nil {
-			return paths
+			return
 		}
 		if !p.forward {
 			ordered.Reverse(path)
 		}
-		return append(paths, path)
+		fn(path)
+		if !p.forward {
+			ordered.Reverse(path)
+		}
+		return
 	}
 	first := true
+	var seenWork []bool
 	for _, n := range p.at(from, to) {
 		if seen[n] {
 			continue
 		}
 		if first {
-			path = append([]graph.Node(nil), path...)
+			p := make([]graph.Node, len(path), len(path)+1)
+			copy(p, path)
+			path = p
+			seenWork = make([]bool, len(seen))
 			first = false
 		}
 		if p.forward {
@@ -719,10 +791,9 @@
 		} else {
 			to = n
 		}
-		path = path[:len(path):len(path)]
-		paths = p.allBetween(from, to, append([]bool(nil), seen...), append(path, p.nodes[n]), paths)
+		copy(seenWork, seen)
+		p.allBetween(from, to, seenWork, append(path, p.nodes[n]), fn)
 	}
-	return paths
 }
 
 type node int64
diff --git a/graph/path/shortest_test.go b/graph/path/shortest_test.go
new file mode 100644
index 0000000..6eb3907
--- /dev/null
+++ b/graph/path/shortest_test.go
@@ -0,0 +1,304 @@
+// Copyright ©2023 The Gonum Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package path
+
+import (
+	"fmt"
+	"math"
+	"reflect"
+	"testing"
+
+	"golang.org/x/exp/rand"
+
+	"gonum.org/v1/gonum/graph"
+	"gonum.org/v1/gonum/graph/graphs/gen"
+	"gonum.org/v1/gonum/graph/internal/ordered"
+	"gonum.org/v1/gonum/graph/simple"
+)
+
+var shortestTests = []struct {
+	n, d int
+	p    float64
+	seed uint64
+}{
+	{n: 100, d: 2, p: 0.5, seed: 1},
+	{n: 200, d: 2, p: 0.5, seed: 1},
+	{n: 100, d: 4, p: 0.25, seed: 1},
+	{n: 200, d: 4, p: 0.25, seed: 1},
+	{n: 100, d: 16, p: 0.1, seed: 1},
+	{n: 200, d: 16, p: 0.1, seed: 1},
+}
+
+func TestShortestAlts(t *testing.T) {
+	for _, test := range shortestTests {
+		t.Run(fmt.Sprintf("AllTo_%d×%d|%v", test.n, test.d, test.p), func(t *testing.T) {
+			g := simple.NewDirectedGraph()
+			gen.SmallWorldsBB(g, test.n, test.d, test.p, rand.New(rand.NewSource(test.seed)))
+			all := allShortest(DijkstraAllPaths(g))
+
+			for uid := int64(0); uid < int64(test.n); uid++ {
+				p := DijkstraAllFrom(g.Node(uid), g)
+				for vid := int64(0); vid < int64(test.n); vid++ {
+					got, gotW := p.AllTo(vid)
+					want, wantW := all.AllBetween(uid, vid)
+					if gotW != wantW {
+						t.Errorf("mismatched weight: got:%f want:%f", gotW, wantW)
+						continue
+					}
+
+					var gotPaths [][]int64
+					if len(got) != 0 {
+						gotPaths = make([][]int64, len(got))
+					}
+					for i, p := range got {
+						for _, v := range p {
+							gotPaths[i] = append(gotPaths[i], v.ID())
+						}
+					}
+					ordered.BySliceValues(gotPaths)
+					var wantPaths [][]int64
+					if len(want) != 0 {
+						wantPaths = make([][]int64, len(want))
+					}
+					for i, p := range want {
+						for _, v := range p {
+							wantPaths[i] = append(wantPaths[i], v.ID())
+						}
+					}
+					ordered.BySliceValues(wantPaths)
+					if !reflect.DeepEqual(gotPaths, wantPaths) {
+						t.Errorf("unexpected shortest paths %d --> %d:\ngot: %v\nwant:%v",
+							uid, vid, gotPaths, wantPaths)
+					}
+				}
+			}
+		})
+	}
+}
+
+func TestAllShortest(t *testing.T) {
+	for _, test := range shortestTests {
+		t.Run(fmt.Sprintf("AllBetween_%d×%d|%v", test.n, test.d, test.p), func(t *testing.T) {
+			g := simple.NewDirectedGraph()
+			gen.SmallWorldsBB(g, test.n, test.d, test.p, rand.New(rand.NewSource(test.seed)))
+
+			p := DijkstraAllPaths(g)
+			for uid := int64(0); uid < int64(test.n); uid++ {
+				for vid := int64(0); vid < int64(test.n); vid++ {
+					got, gotW := p.AllBetween(uid, vid)
+					want, wantW := allShortest(p).AllBetween(uid, vid) // Compare to naive.
+					if gotW != wantW {
+						t.Errorf("mismatched weight: got:%f want:%f", gotW, wantW)
+						continue
+					}
+
+					var gotPaths [][]int64
+					if len(got) != 0 {
+						gotPaths = make([][]int64, len(got))
+					}
+					for i, p := range got {
+						for _, v := range p {
+							gotPaths[i] = append(gotPaths[i], v.ID())
+						}
+					}
+					ordered.BySliceValues(gotPaths)
+					var wantPaths [][]int64
+					if len(want) != 0 {
+						wantPaths = make([][]int64, len(want))
+					}
+					for i, p := range want {
+						for _, v := range p {
+							wantPaths[i] = append(wantPaths[i], v.ID())
+						}
+					}
+					ordered.BySliceValues(wantPaths)
+					if !reflect.DeepEqual(gotPaths, wantPaths) {
+						t.Errorf("unexpected shortest paths %d --> %d:\ngot: %v\nwant:%v",
+							uid, vid, gotPaths, wantPaths)
+					}
+				}
+			}
+		})
+	}
+}
+
+// allShortest implements an allocation-naive AllBetween.
+type allShortest AllShortest
+
+// at returns a slice of node indexes into p.nodes for nodes that are mid points
+// between nodes indexed by from and to.
+func (p allShortest) at(from, to int) (mid []int) {
+	return p.next[from+to*len(p.nodes)]
+}
+
+// AllBetween returns all shortest paths from u to v and the weight of the paths. Paths
+// containing zero-weight cycles are not returned. If a negative cycle exists between
+// u and v, paths is returned nil and weight is returned as -Inf.
+func (p allShortest) AllBetween(uid, vid int64) (paths [][]graph.Node, weight float64) {
+	from, fromOK := p.indexOf[uid]
+	to, toOK := p.indexOf[vid]
+	if !fromOK || !toOK || len(p.at(from, to)) == 0 {
+		if uid == vid {
+			if !fromOK {
+				return [][]graph.Node{{node(uid)}}, 0
+			}
+			return [][]graph.Node{{p.nodes[from]}}, 0
+		}
+		return nil, math.Inf(1)
+	}
+
+	weight = p.dist.At(from, to)
+	if math.Float64bits(weight) == defacedBits {
+		return nil, math.Inf(-1)
+	}
+
+	var n graph.Node
+	if p.forward {
+		n = p.nodes[from]
+	} else {
+		n = p.nodes[to]
+	}
+	seen := make([]bool, len(p.nodes))
+	paths = p.allBetween(from, to, seen, []graph.Node{n}, nil)
+
+	return paths, weight
+}
+
+// allBetween recursively constructs a slice of paths extending from the node
+// indexed into p.nodes by from to the node indexed by to. len(seen) must match
+// the number of nodes held by the receiver. The path parameter is the current
+// working path and the results are written into paths.
+func (p allShortest) allBetween(from, to int, seen []bool, path []graph.Node, paths [][]graph.Node) [][]graph.Node {
+	if p.forward {
+		seen[from] = true
+	} else {
+		seen[to] = true
+	}
+	if from == to {
+		if path == nil {
+			return paths
+		}
+		if !p.forward {
+			ordered.Reverse(path)
+		}
+		return append(paths, path)
+	}
+	first := true
+	for _, n := range p.at(from, to) {
+		if seen[n] {
+			continue
+		}
+		if first {
+			path = append([]graph.Node(nil), path...)
+			first = false
+		}
+		if p.forward {
+			from = n
+		} else {
+			to = n
+		}
+		path = path[:len(path):len(path)]
+		paths = p.allBetween(from, to, append([]bool(nil), seen...), append(path, p.nodes[n]), paths)
+	}
+	return paths
+}
+
+var shortestBenchmarks = []struct {
+	n, d int
+	p    float64
+	seed uint64
+}{
+	{n: 100, d: 2, p: 0.5, seed: 1},
+	{n: 1000, d: 2, p: 0.5, seed: 1},
+	{n: 100, d: 4, p: 0.25, seed: 1},
+	{n: 1000, d: 4, p: 0.25, seed: 1},
+	{n: 100, d: 16, p: 0.1, seed: 1},
+	{n: 1000, d: 16, p: 0.1, seed: 1},
+}
+
+func BenchmarkShortestAlts(b *testing.B) {
+	for _, bench := range shortestBenchmarks {
+		g := simple.NewDirectedGraph()
+		gen.SmallWorldsBB(g, bench.n, bench.d, bench.p, rand.New(rand.NewSource(bench.seed)))
+
+		// Find the widest path set.
+		var (
+			bestP   ShortestAlts
+			bestVid int64
+			n       int
+		)
+		for uid := int64(0); uid < int64(bench.n); uid++ {
+			p := DijkstraAllFrom(g.Node(uid), g)
+			for vid := int64(0); vid < int64(bench.n); vid++ {
+				paths, _ := p.AllTo(vid)
+				if len(paths) > n {
+					n = len(paths)
+					bestP = p
+					bestVid = vid
+				}
+			}
+		}
+
+		b.Run(fmt.Sprintf("AllTo_%d×%d|%v(%d)", bench.n, bench.d, bench.p, n), func(b *testing.B) {
+			for i := 0; i < b.N; i++ {
+				paths, _ := bestP.AllTo(bestVid)
+				if len(paths) != n {
+					b.Errorf("unexpected number of paths: got:%d want:%d", len(paths), n)
+				}
+			}
+		})
+		b.Run(fmt.Sprintf("AllToFunc_%d×%d|%v(%d)", bench.n, bench.d, bench.p, n), func(b *testing.B) {
+			for i := 0; i < b.N; i++ {
+				var paths int
+				bestP.AllToFunc(bestVid, func(_ []graph.Node) { paths++ })
+				if paths != n {
+					b.Errorf("unexpected number of paths: got:%d want:%d", paths, n)
+				}
+			}
+		})
+	}
+}
+
+func BenchmarkAllShortest(b *testing.B) {
+	for _, bench := range shortestBenchmarks {
+		g := simple.NewDirectedGraph()
+		gen.SmallWorldsBB(g, bench.n, bench.d, bench.p, rand.New(rand.NewSource(bench.seed)))
+		p := DijkstraAllPaths(g)
+
+		// Find the widest path set.
+		var (
+			bestUid, bestVid int64
+			n                int
+		)
+		for uid := int64(0); uid < int64(bench.n); uid++ {
+			for vid := int64(0); vid < int64(bench.n); vid++ {
+				paths, _ := p.AllBetween(uid, vid)
+				if len(paths) > n {
+					n = len(paths)
+					bestUid = uid
+					bestVid = vid
+				}
+			}
+		}
+
+		b.Run(fmt.Sprintf("AllBetween_%d×%d|%v(%d)", bench.n, bench.d, bench.p, n), func(b *testing.B) {
+			for i := 0; i < b.N; i++ {
+				paths, _ := p.AllBetween(bestUid, bestVid)
+				if len(paths) != n {
+					b.Errorf("unexpected number of paths: got:%d want:%d", len(paths), n)
+				}
+			}
+		})
+		b.Run(fmt.Sprintf("AllBetweenFunc_%d×%d|%v(%d)", bench.n, bench.d, bench.p, n), func(b *testing.B) {
+			for i := 0; i < b.N; i++ {
+				var paths int
+				p.AllBetweenFunc(bestUid, bestVid, func(_ []graph.Node) { paths++ })
+				if paths != n {
+					b.Errorf("unexpected number of paths: got:%d want:%d", paths, n)
+				}
+			}
+		})
+	}
+}