graph/path: Add single-pair shortest path variant

This variant can terminate early when the target is reached. This can make a large difference in running time for Yen's k-shortest paths algorithm, as it makes many calls to the shortest path subroutine.
gonum · Nov 28, 2024 · c736b6a · c736b6a
1 parent c2ad6d4
commit c736b6a
Show file tree

Hide file tree

Showing 3 changed files with 74 additions and 23 deletions.
diff --git 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 v in the graph g. The
+// result is equivalent to DijkstraFrom(u, g).To(v), but DijkstraFromTo can be
+// more efficient, as it can terminate early if v 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 v.
+//
+// The time complexity of DijkstraFromTo is O(|E|.log|V|).
+func DijkstraFromTo(u graph.Node, v 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 v == nil {
+		panic("dijkstra: nil target node")
+	}
+	return dijkstraFrom(u, v, g).To(v.ID())
+}
+
+// Shared implementation of DijkstraFrom and DijkstraFromTo.
+func dijkstraFrom(u, target 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); target == 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 target != nil && mnid == target.ID() {
+			break
+		}
 		to := g.From(mnid)
 		for to.Next() {
 			v := to.Node()

diff --git a/graph/path/dijkstra_test.go b/graph/path/dijkstra_test.go
@@ -24,6 +24,29 @@ func TestDijkstraFrom(t *testing.T) {
 			g.SetWeightedEdge(e)
 		}
 
+		checkPath := func(typ string, p []graph.Node, weight float64) {
+			if weight != test.Weight {
+				t.Errorf("%q %s: unexpected weight from To: got:%f want:%f",
+					test.Name, typ, weight, test.Weight)
+			}
+
+			var got []int64
+			for _, n := range p {
+				got = append(got, n.ID())
+			}
+			ok := len(got) == 0 && len(test.WantPaths) == 0
+			for _, sp := range test.WantPaths {
+				if reflect.DeepEqual(got, sp) {
+					ok = true
+					break
+				}
+			}
+			if !ok {
+				t.Errorf("%q %s: unexpected shortest path:\ngot: %v\nwant from:%v",
+					test.Name, typ, p, test.WantPaths)
+			}
+		}
+
 		for _, tg := range []struct {
 			typ string
 			g   traverse.Graph
@@ -56,38 +79,41 @@ func TestDijkstraFrom(t *testing.T) {
 				t.Fatalf("%q %s: unexpected from node ID: got:%d want:%d", test.Name, tg.typ, pt.From().ID(), test.Query.From().ID())
 			}
 
-			p, weight := pt.To(test.Query.To().ID())
-			if weight != test.Weight {
-				t.Errorf("%q %s: unexpected weight from To: got:%f want:%f",
-					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",
 					test.Name, tg.typ, weight, test.Weight)
 			}
 
-			var got []int64
-			for _, n := range p {
-				got = append(got, n.ID())
-			}
-			ok := len(got) == 0 && len(test.WantPaths) == 0
-			for _, sp := range test.WantPaths {
-				if reflect.DeepEqual(got, sp) {
-					ok = true
-					break
-				}
-			}
-			if !ok {
-				t.Errorf("%q %s: unexpected shortest path:\ngot: %v\nwant from:%v",
-					test.Name, tg.typ, p, test.WantPaths)
-			}
+			p, weight := pt.To(test.Query.To().ID())
+			checkPath(tg.typ, p, weight)
 
 			np, weight := pt.To(test.NoPathFor.To().ID())
 			if pt.From().ID() == test.NoPathFor.From().ID() && (np != nil || !math.IsInf(weight, 1)) {
 				t.Errorf("%q %s: unexpected path:\ngot: path=%v weight=%f\nwant:path=<nil> weight=+Inf",
 					test.Name, tg.typ, np, weight)
 			}
 		}
+
+		// Test the single-destination variant.
+		var (
+			p        []graph.Node
+			weight   float64
+			panicked bool
+		)
+		func() {
+			defer func() {
+				panicked = recover() != nil
+			}()
+			p, weight = DijkstraFromTo(test.Query.From(), test.Query.To(), g.(graph.Graph))
+		}()
+		if panicked || test.HasNegativeWeight {
+			if !test.HasNegativeWeight {
+				t.Errorf("%q: unexpected panic", test.Name)
+			}
+			continue
+		}
+
+		checkPath("from-to", p, weight)
 	}
 }
 

diff --git 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
 			}