graph/path: Implement standard improvements to Yen's KSP algorithm

1) Lawler's modification 2) Early termination See https://en.wikipedia.org/wiki/Yen%27s_algorithm#Improvements
gonum · Nov 28, 2024 · 1ed9bd6 · 1ed9bd6
1 parent c736b6a
commit 1ed9bd6
Show file tree

Hide file tree

Showing 2 changed files with 62 additions and 25 deletions.
diff --git a/graph/path/yen_ksp.go b/graph/path/yen_ksp.go
@@ -43,61 +43,61 @@ func YenKShortestPaths(g graph.Graph, k int, cost float64, s, t graph.Node) [][]
 	}
 	paths := [][]graph.Node{shortest}
 
+	// For Lawler's modification
+	// The index of the spur node in the previous shortest path
+	spurIndex := 0
 	var pot []yenShortest
 	var root []graph.Node
-	for i := int64(1); k < 0 || i < int64(k); i++ {
-		// The spur node ranges from the first node to the next
+	for i := 1; k < 0 || i < k; i++ {
+		// The spur node ranges from the previous spur node to the next
 		// to last node in the previous k-shortest path.
-		for n := 0; n < len(paths[i-1])-1; n++ {
+		prevPath := paths[i-1]
+		root = append(root[:0], prevPath[:spurIndex]...)
+		for n := spurIndex; n < len(prevPath)-1; n++ {
 			yk.reset()
 
-			spur := paths[i-1][n]
-			root := append(root[:0], paths[i-1][:n+1]...)
+			spur := prevPath[n]
+			root = append(root, spur)
 
 			for _, path := range paths {
 				if len(path) <= n {
 					continue
 				}
-				ok := true
-				for x := 0; x < len(root); x++ {
+				// check if the paths agree up to the spur node
+				for x := 0; x <= n; x++ {
 					if path[x].ID() != root[x].ID() {
-						ok = false
-						break
+						goto disagree
 					}
 				}
-				if ok {
-					yk.removeEdge(path[n].ID(), path[n+1].ID())
-				}
+				yk.removeEdge(path[n].ID(), path[n+1].ID())
+			disagree:
 			}
-			for _, u := range root[:len(root)-1] {
+			for _, u := range root[:n] {
 				yk.removeNode(u.ID())
 			}
 
 			spath, weight := DijkstraFromTo(spur, t, yk)
 			if weight > cost || math.IsInf(weight, 1) {
 				continue
 			}
-			if len(root) > 1 {
+			if n > 0 {
 				var rootWeight float64
-				for x := 1; x < len(root); x++ {
+				for x := 1; x <= n; x++ {
 					w, _ := yk.weight(root[x-1].ID(), root[x].ID())
 					rootWeight += w
 				}
-				spath = append(root[:len(root)-1], spath...)
+				spath = append(root[:n], spath...)
 				weight += rootWeight
 			}
 
 			// Add the potential k-shortest path if it is new.
-			isNewPot := true
 			for x := range pot {
 				if isSamePath(pot[x].path, spath) {
-					isNewPot = false
-					break
+					goto notnew
 				}
 			}
-			if isNewPot {
-				pot = append(pot, yenShortest{spath, weight})
-			}
+			pot = append(pot, yenShortest{spath, weight, n})
+		notnew:
 		}
 
 		if len(pot) == 0 {
@@ -111,7 +111,16 @@ func YenKShortestPaths(g graph.Graph, k int, cost float64, s, t graph.Node) [][]
 		if len(best.path) <= 1 || best.weight > cost {
 			break
 		}
+		if neededPaths := k - i; k >= 0 && len(pot) >= neededPaths && best.weight == pot[neededPaths-1].weight {
+			// Terminate early if we have found k-i paths with the same minimum weight.
+			// All subsequent deviations will have the same or greater weight.
+			for j := 0; j < neededPaths; j++ {
+				paths = append(paths, pot[j].path)
+			}
+			break
+		}
 		paths = append(paths, best.path)
+		spurIndex = best.spurIndex
 		pot = pot[1:]
 	}
 
@@ -131,10 +140,11 @@ func isSamePath(a, b []graph.Node) bool {
 	return true
 }
 
-// yenShortest holds a path and its weight for sorting.
+// yenShortest holds a path, its spurIndex and its weight for sorting.
 type yenShortest struct {
-	path   []graph.Node
-	weight float64
+	path      []graph.Node
+	weight    float64
+	spurIndex int
 }
 
 // yenKSPAdjuster allows walked edges to be omitted from a graph

diff --git a/graph/path/yen_ksp_test.go b/graph/path/yen_ksp_test.go
@@ -329,6 +329,33 @@ var yenShortestPathTests = []struct {
 			{1, 4, 5, 2, 3, 6},
 		},
 	},
+	{
+		// 1st shortest path: 1 -> 2 -> 3 (cost: 2)
+		// Shortest deviations: 1 -> 4 -> 3 (cost: 3), 1 -> 2 -> 6 -> 3 (cost: 11)
+		// 2nd shortest path: 1 -> 4 -> 3
+		// New deviation: 1 -> 4 -> 5 -> 3 (cost: 4) (shorter than 1 -> 2 -> 6 -> 3)
+		name: "new_shorter_deviation",
+		graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
+		edges: []simple.WeightedEdge{
+			{F: simple.Node(1), T: simple.Node(2), W: 1},
+			{F: simple.Node(2), T: simple.Node(3), W: 1},
+			{F: simple.Node(2), T: simple.Node(6), W: 5},
+			{F: simple.Node(6), T: simple.Node(3), W: 5},
+			{F: simple.Node(1), T: simple.Node(4), W: 1},
+			{F: simple.Node(4), T: simple.Node(3), W: 2},
+			{F: simple.Node(4), T: simple.Node(5), W: 1},
+			{F: simple.Node(5), T: simple.Node(3), W: 2},
+		},
+		k: 4,
+		query: simple.Edge{F: simple.Node(1), T: simple.Node(3)},
+		cost: math.Inf(1),
+		wantPaths: [][]int64{
+			{1, 2, 3},
+			{1, 4, 3},
+			{1, 4, 5, 3},
+			{1, 2, 6, 3},
+		},
+	},
 }
 
 func bipartite(n int, weight, inc float64) []simple.WeightedEdge {