src

Go monorepo.
git clone git://code.dwrz.net/src
Log | Files | Refs

shortest.go (1011B)

      1 // Copyright 2026 The Go Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style
      3 // license that can be found in the LICENSE file.
      4 
      5 package graph
      6 
      7 import "slices"
      8 
      9 // ShortestPath returns a shortest path from src to dst in g.
     10 // It returns the path as a slice of nodes starting with src and ending with dst.
     11 // If no path is found, it returns nil.
     12 func ShortestPath[NodeID comparable](g Graph[NodeID], src, dst NodeID) []NodeID {
     13 	if src == dst {
     14 		return []NodeID{src}
     15 	}
     16 
     17 	pred := make(map[NodeID]NodeID)
     18 	queue := []NodeID{src}
     19 	// Mark src as seen.
     20 	pred[src] = src
     21 
     22 	for len(queue) > 0 {
     23 		n := queue[0]
     24 		queue = queue[1:]
     25 
     26 		if n == dst {
     27 			// Reconstruct path
     28 			var path []NodeID
     29 			for curr := dst; curr != src; curr = pred[curr] {
     30 				path = append(path, curr)
     31 			}
     32 			path = append(path, src)
     33 			slices.Reverse(path)
     34 			return path
     35 		}
     36 
     37 		for v := range g.Out(n) {
     38 			if _, seen := pred[v]; !seen {
     39 				pred[v] = n
     40 				queue = append(queue, v)
     41 			}
     42 		}
     43 	}
     44 	return nil
     45 }