Repository: gonum/gonum
Pull request #2012 (2025-01-14 11:27:42)

A+C: add Oskar Haarklou Veileborg


Patch:
diff --git a/AUTHORS b/AUTHORS
index dc7e93d0..30ffdc61 100644
--- a/AUTHORS
+++ b/AUTHORS
@@ -25,6 +25,7 @@ Chris Tessum <ctessum@gmail.com>
 Christophe Meessen <christophe.meessen@gmail.com>
 Christopher Waldon <christopher.waldon.dev@gmail.com>
 Clayton Northey <clayton.northey@gmail.com>
+Coana ApS
 Dan Kortschak <dan.kortschak@adelaide.edu.au> <dan@kortschak.io>
 Daniel Fireman <danielfireman@gmail.com>
 Dario Heinisch <dario.heinisch@gmail.com>
diff --git a/CONTRIBUTORS b/CONTRIBUTORS
index bf429a49..e61106f5 100644
--- a/CONTRIBUTORS
+++ b/CONTRIBUTORS
@@ -105,6 +105,7 @@ Nick Potts <nick@the-potts.com>
 Nils Wogatzky <odog@netcologne.de>
 Olivier Wulveryck <olivier.wulveryck@gmail.com>
 Or Rikon <rikonor@gmail.com>
+Oskar Haarklou Veileborg <ohv1020@hotmail.com>
 Patricio Whittingslow <graded.sp@gmail.com>
 Patrick DeVivo <patrick@tickgit.com>
 Pontus Melke <pontusmelke@gmail.com>
diff --git a/graph/path/dijkstra.go b/graph/path/dijkstra.go
index 96faa816..7ba8395d 100644
--- a/graph/path/dijkstra.go
+++ b/graph/path/dijkstra.go
@@ -20,8 +20,30 @@ import (
 //
 // The time complexity of DijkstraFrom is O(|E|.log|V|).
 func DijkstraFrom(u graph.Node, g traverse.Graph) Shortest {
+	return dijkstraFrom(u, nil, g)
+}
+
+// DijkstraFromTo returns a shortest path from u to t in the graph g. The
+// result is equivalent to DijkstraFrom(u, g).To(t.ID()), but DijkstraFromTo
+// can be more efficient, as it can terminate early if t is reached. If the
+// graph does not implement Weighted, UniformCost is used. DijkstraFromTo will
+// panic if g has a u-reachable negative edge weight that is discovered before
+// reaching t.
+//
+// The time complexity of DijkstraFromTo is O(|E|.log|V|).
+func DijkstraFromTo(u, t graph.Node, g traverse.Graph) (path []graph.Node, weight float64) {
+	// An implementation of Bidirectional Dijkstra's algorithm could be even
+	// more efficient, but it requires a transposed (or undirected) graph.
+	if t == nil {
+		panic("dijkstra: nil target node")
+	}
+	return dijkstraFrom(u, t, g).To(t.ID())
+}
+
+func dijkstraFrom(u, t graph.Node, g traverse.Graph) Shortest {
 	var path Shortest
-	if h, ok := g.(graph.Graph); ok {
+	// Use the incremental version when a target is provided.
+	if h, ok := g.(graph.Graph); t == nil && ok {
 		if h.Node(u.ID()) == nil {
 			return Shortest{from: u}
 		}
@@ -58,6 +80,9 @@ func DijkstraFrom(u graph.Node, g traverse.Graph) Shortest {
 			continue
 		}
 		mnid := mid.node.ID()
+		if t != nil && mnid == t.ID() {
+			break
+		}
 		to := g.From(mnid)
 		for to.Next() {
 			v := to.Node()
diff --git a/graph/path/yen_ksp.go b/graph/path/yen_ksp.go
index b6cb660f..7bc38752 100644
--- a/graph/path/yen_ksp.go
+++ b/graph/path/yen_ksp.go
@@ -33,7 +33,7 @@ func YenKShortestPaths(g graph.Graph, k int, cost float64, s, t graph.Node) [][]
 		yk.weight = UniformCost(g)
 	}
 
-	shortest, weight := DijkstraFrom(s, yk).To(t.ID())
+	shortest, weight := DijkstraFromTo(s, t, yk)
 	cost += weight // Set cost to absolute cost limit.
 	switch len(shortest) {
 	case 0:
@@ -73,7 +73,7 @@ func YenKShortestPaths(g graph.Graph, k int, cost float64, s, t graph.Node) [][]
 				yk.removeNode(u.ID())
 			}
 
-			spath, weight := DijkstraFrom(spur, yk).To(t.ID())
+			spath, weight := DijkstraFromTo(spur, t, yk)
 			if weight > cost || math.IsInf(weight, 1) {
 				continue
 			}


Test patch:
diff --git a/graph/path/dijkstra_test.go b/graph/path/dijkstra_test.go
index 99762bbf..bab2d2d8 100644
--- a/graph/path/dijkstra_test.go
+++ b/graph/path/dijkstra_test.go
@@ -27,9 +27,11 @@ func TestDijkstraFrom(t *testing.T) {
 		for _, tg := range []struct {
 			typ string
 			g   traverse.Graph
+			t   graph.Node
 		}{
-			{"complete", g.(graph.Graph)},
-			{"incremental", incremental{g.(graph.Weighted)}},
+			{"complete", g.(graph.Graph), nil},
+			{"incremental", incremental{g.(graph.Weighted)}, nil},
+			{"single-destination", g.(graph.Graph), test.Query.To()},
 		} {
 			var (
 				pt Shortest
@@ -40,13 +42,13 @@ func TestDijkstraFrom(t *testing.T) {
 				defer func() {
 					panicked = recover() != nil
 				}()
-				pt = DijkstraFrom(test.Query.From(), tg.g)
+				pt = dijkstraFrom(test.Query.From(), tg.t, tg.g)
 			}()
 			if panicked || test.HasNegativeWeight {
 				if !test.HasNegativeWeight {
 					t.Errorf("%q %s: unexpected panic", test.Name, tg.typ)
 				}
-				if !panicked {
+				if !panicked && tg.t == nil {
 					t.Errorf("%q %s: expected panic for negative edge weight", test.Name, tg.typ)
 				}
 				continue
@@ -62,7 +64,7 @@ func TestDijkstraFrom(t *testing.T) {
 					test.Name, tg.typ, weight, test.Weight)
 			}
 			if weight := pt.WeightTo(test.Query.To().ID()); weight != test.Weight {
-				t.Errorf("%q %s: unexpected weight from Weight: got:%f want:%f",
+				t.Errorf("%q %s: unexpected weight from WeightTo: got:%f want:%f",
 					test.Name, tg.typ, weight, test.Weight)
 			}