## package path

`import "gonum.org/v1/gonum/graph/path"`

Package path provides graph path finding functions.

### Index ¶

- func Kruskal(dst WeightedBuilder, g UndirectedWeightLister) float64
- func NullHeuristic(_, _ graph.Node) float64
- func Prim(dst WeightedBuilder, g graph.WeightedUndirected) float64
- func YenKShortestPaths(g graph.Graph, k int, cost float64, s, t graph.Node) [][]graph.Node
- type AllShortest
- func DijkstraAllPaths(g graph.Graph) (paths AllShortest)
- func FloydWarshall(g graph.Graph) (paths AllShortest, ok bool)
- func JohnsonAllPaths(g graph.Graph) (paths AllShortest, ok bool)
- func (p AllShortest) AllBetween(uid, vid int64) (paths [][]graph.Node, weight float64)
- func (p AllShortest) AllBetweenFunc(uid, vid int64, fn func(path []graph.Node))
- func (p AllShortest) Between(uid, vid int64) (path []graph.Node, weight float64, unique bool)
- func (p AllShortest) Weight(uid, vid int64) float64
- type Heuristic
- type HeuristicCoster
- type Shortest
- func AStar(s, t graph.Node, g traverse.Graph, h Heuristic) (path Shortest, expanded int)
- func BellmanFordFrom(u graph.Node, g traverse.Graph) (path Shortest, ok bool)
- func DijkstraFrom(u graph.Node, g traverse.Graph) Shortest
- func (p Shortest) From() graph.Node
- func (p Shortest) To(vid int64) (path []graph.Node, weight float64)
- func (p Shortest) WeightTo(vid int64) float64
- type ShortestAlts
- func BellmanFordAllFrom(u graph.Node, g traverse.Graph) (path ShortestAlts, ok bool)
- func DijkstraAllFrom(u graph.Node, g traverse.Graph) ShortestAlts
- func (p ShortestAlts) AllTo(vid int64) (paths [][]graph.Node, weight float64)
- func (p ShortestAlts) AllToFunc(vid int64, fn func(path []graph.Node))
- func (p ShortestAlts) From() graph.Node
- func (p ShortestAlts) To(vid int64) (path []graph.Node, weight float64, unique bool)
- func (p ShortestAlts) WeightTo(vid int64) float64
- type UndirectedWeightLister
- type Weighted
- type WeightedBuilder
- type Weighting

#### Examples ¶

### Functions ¶

#### func Kruskal ¶

func Kruskal(dst WeightedBuilder, g UndirectedWeightLister) float64

Kruskal generates a minimum spanning tree of g by greedy tree coalescence, placing the result in the destination, dst. If the edge weights of g are distinct it will be the unique minimum spanning tree of g. The destination is not cleared first. The weight of the minimum spanning tree is returned. If g is not connected, a minimum spanning forest will be constructed in dst and the sum of minimum spanning tree weights will be returned.

Nodes and Edges from g are used to construct dst, so if the Node and Edge types used in g are pointer or reference-like, then the values will be shared between the graphs.

If dst has nodes that exist in g, Kruskal will panic.

#### func NullHeuristic ¶

NullHeuristic is an admissible, consistent heuristic that will not speed up computation.

#### func Prim ¶

func Prim(dst WeightedBuilder, g graph.WeightedUndirected) float64

Prim generates a minimum spanning tree of g by greedy tree extension, placing the result in the destination, dst. If the edge weights of g are distinct it will be the unique minimum spanning tree of g. The destination is not cleared first. The weight of the minimum spanning tree is returned. If g is not connected, a minimum spanning forest will be constructed in dst and the sum of minimum spanning tree weights will be returned.

Nodes and Edges from g are used to construct dst, so if the Node and Edge types used in g are pointer or reference-like, then the values will be shared between the graphs.

If dst has nodes that exist in g, Prim will panic.

#### func YenKShortestPaths ¶

YenKShortestPaths returns the k-shortest loopless paths from s to t in g with path costs no greater than cost beyond the shortest path. If k is negative, only path cost will be used to limit the set of returned paths. YenKShortestPaths will panic if g contains a negative edge weight.

### Types ¶

#### type AllShortest ¶

```
type AllShortest struct {
// contains filtered or unexported fields
}
```

AllShortest is a shortest-path tree created by the DijkstraAllPaths, FloydWarshall or JohnsonAllPaths all-pairs shortest paths functions.

#### func DijkstraAllPaths ¶

func DijkstraAllPaths(g graph.Graph) (paths AllShortest)

DijkstraAllPaths returns a shortest-path tree for shortest paths in the graph g. If the graph does not implement graph.Weighter, UniformCost is used. DijkstraAllPaths will panic if g has a negative edge weight.

The time complexity of DijkstraAllPaths is O(|V|.|E|+|V|^2.log|V|).

#### func FloydWarshall ¶

func FloydWarshall(g graph.Graph) (paths AllShortest, ok bool)

FloydWarshall returns a shortest-path tree for the graph g or false indicating that a negative cycle exists in the graph. If a negative cycle exists in the graph the returned paths will be valid and edge weights on the negative cycle will be set to -Inf. If the graph does not implement Weighted, UniformCost is used.

The time complexity of FloydWarshall is O(|V|^3).

## Example (Negativecycles)¶

Code:play

package main import ( "fmt" "math" "gonum.org/v1/gonum/graph/path" "gonum.org/v1/gonum/graph/simple" ) func main() { // FloydWarshall can be used to find an exhaustive // set of nodes in negative cycles in a graph. // Construct a graph with a negative cycle. edges := []simple.WeightedEdge{ {F: simple.Node('a'), T: simple.Node('f'), W: -1}, {F: simple.Node('b'), T: simple.Node('a'), W: 1}, {F: simple.Node('b'), T: simple.Node('c'), W: -1}, {F: simple.Node('b'), T: simple.Node('d'), W: 1}, {F: simple.Node('c'), T: simple.Node('b'), W: 0}, {F: simple.Node('e'), T: simple.Node('a'), W: 1}, {F: simple.Node('f'), T: simple.Node('e'), W: -1}, } g := simple.NewWeightedDirectedGraph(0, math.Inf(1)) for _, e := range edges { g.SetWeightedEdge(e) } // Find the shortest path to each node from Q. pt, ok := path.FloydWarshall(g) if ok { fmt.Println("no negative cycle present") return } ids := []int64{'a', 'b', 'c', 'd', 'e', 'f'} for _, id := range ids { if math.IsInf(pt.Weight(id, id), -1) { fmt.Printf("%c is in a negative cycle\n", id) } } for _, uid := range ids { for _, vid := range ids { _, w, unique := pt.Between(uid, vid) if math.IsInf(w, -1) { fmt.Printf("negative cycle in path from %c to %c unique=%t\n", uid, vid, unique) } } } }

Output:

a is in a negative cycle b is in a negative cycle c is in a negative cycle e is in a negative cycle f is in a negative cycle negative cycle in path from a to a unique=false negative cycle in path from a to e unique=false negative cycle in path from a to f unique=false negative cycle in path from b to a unique=false negative cycle in path from b to b unique=false negative cycle in path from b to c unique=false negative cycle in path from b to d unique=false negative cycle in path from b to e unique=false negative cycle in path from b to f unique=false negative cycle in path from c to a unique=false negative cycle in path from c to b unique=false negative cycle in path from c to c unique=false negative cycle in path from c to d unique=false negative cycle in path from c to e unique=false negative cycle in path from c to f unique=false negative cycle in path from e to a unique=false negative cycle in path from e to e unique=false negative cycle in path from e to f unique=false negative cycle in path from f to a unique=false negative cycle in path from f to e unique=false negative cycle in path from f to f unique=false

#### func JohnsonAllPaths ¶

func JohnsonAllPaths(g graph.Graph) (paths AllShortest, ok bool)

JohnsonAllPaths returns a shortest-path tree for shortest paths in the graph g. If the graph does not implement Weighted, UniformCost is used. If a negative cycle exists in g, ok will be returned false and paths will not contain valid data.

The time complexity of JohnsonAllPaths is O(|V|.|E|+|V|^2.log|V|).

#### func (AllShortest) AllBetween ¶

func (p AllShortest) AllBetween(uid, vid int64) (paths [][]graph.Node, weight float64)

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 (AllShortest) AllBetweenFunc ¶

func (p AllShortest) AllBetweenFunc(uid, vid int64, fn func(path []graph.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 (AllShortest) Between ¶

Between returns a shortest path from u to v and the weight of the path. If more than one shortest path exists between u and v, a randomly chosen path will be returned and unique is returned false. If a cycle with zero weight exists in the path, it will not be included, but unique will be returned false. If a negative cycle exists on the path from u to v, path will be returned nil, weight will be -Inf and unique will be false.

#### func (AllShortest) Weight ¶

func (p AllShortest) Weight(uid, vid int64) float64

Weight returns the weight of the minimum path between u and v.

#### type Heuristic ¶

Heuristic returns an estimate of the cost of travelling between two nodes.

#### type HeuristicCoster ¶

HeuristicCoster wraps the HeuristicCost method. A graph implementing the interface provides a heuristic between any two given nodes.

#### type Shortest ¶

```
type Shortest struct {
// contains filtered or unexported fields
}
```

Shortest is a shortest-path tree created by the BellmanFordFrom, DijkstraFrom or AStar single-source shortest path functions.

#### func AStar ¶

AStar finds the A*-shortest path from s to t in g using the heuristic h. The path and its cost are returned in a Shortest along with paths and costs to all nodes explored during the search. The number of expanded nodes is also returned. This value may help with heuristic tuning.

The path will be the shortest path if the heuristic is admissible. A heuristic is admissible if for any node, n, in the graph, the heuristic estimate of the cost of the path from n to t is less than or equal to the true cost of that path.

If h is nil, AStar will use the g.HeuristicCost method if g implements HeuristicCoster, falling back to NullHeuristic otherwise. If the graph does not implement Weighted, UniformCost is used. AStar will panic if g has an A*-reachable negative edge weight.

#### func BellmanFordFrom ¶

BellmanFordFrom returns a shortest-path tree for a shortest path from u to all nodes in the graph g, or false indicating that a negative cycle exists in the graph. If the graph does not implement Weighted, UniformCost is used.

If g is a graph.Graph, all nodes of the graph will be stored in the shortest-path tree, otherwise only nodes reachable from u will be stored.

The time complexity of BellmanFordFrom is O(|V|.|E|).

## Example (Negativecycles)¶

Code:play

package main import ( "fmt" "math" "gonum.org/v1/gonum/graph" "gonum.org/v1/gonum/graph/path" "gonum.org/v1/gonum/graph/simple" ) func main() { // BellmanFordFrom can be used to find a non-exhaustive // set of negative cycles in a graph. // Construct a graph with a negative cycle. edges := []simple.WeightedEdge{ {F: simple.Node('a'), T: simple.Node('b'), W: -2}, {F: simple.Node('a'), T: simple.Node('f'), W: 2}, {F: simple.Node('b'), T: simple.Node('c'), W: 6}, {F: simple.Node('c'), T: simple.Node('a'), W: -5}, {F: simple.Node('d'), T: simple.Node('c'), W: -3}, {F: simple.Node('d'), T: simple.Node('e'), W: 8}, {F: simple.Node('e'), T: simple.Node('b'), W: 9}, {F: simple.Node('e'), T: simple.Node('c'), W: 2}, } g := simple.NewWeightedDirectedGraph(0, math.Inf(1)) for _, e := range edges { g.SetWeightedEdge(e) } // Add a zero-cost path to all nodes from a new node Q. // Since the graph is being mutated, we get a range over // a slice of the graph's nodes rather than using the // graph.Nodes iterator directly. for _, n := range graph.NodesOf(g.Nodes()) { g.SetWeightedEdge(simple.WeightedEdge{F: simple.Node('Q'), T: n}) } // Find the shortest path to each node from Q. pt, ok := path.BellmanFordFrom(simple.Node('Q'), g) if ok { fmt.Println("no negative cycle present") return } for _, id := range []int64{'a', 'b', 'c', 'd', 'e', 'f'} { p, w := pt.To(id) if math.IsInf(w, -1) { fmt.Printf("negative cycle in path to %c path:%c\n", id, p) } } }

Output:

negative cycle in path to a path:[a b c a] negative cycle in path to b path:[b c a b] negative cycle in path to c path:[c a b c] negative cycle in path to f path:[a b c a f]

#### func DijkstraFrom ¶

DijkstraFrom returns a shortest-path tree for a shortest path from u to all nodes in the graph g. If the graph does not implement Weighted, UniformCost is used. DijkstraFrom will panic if g has a u-reachable negative edge weight.

If g is a graph.Graph, all nodes of the graph will be stored in the shortest-path tree, otherwise only nodes reachable from u will be stored.

The time complexity of DijkstraFrom is O(|E|.log|V|).

#### func (Shortest) From ¶

From returns the starting node of the paths held by the Shortest.

#### func (Shortest) To ¶

To returns a shortest path to v and the weight of the path. If the path to v includes a negative cycle, one pass through the cycle will be included in path, but any path leading into the negative cycle will be lost, and weight will be returned as -Inf.

#### func (Shortest) WeightTo ¶

WeightTo returns the weight of the minimum path to v. If the path to v includes a negative cycle, the returned weight will not reflect the true path weight.

#### type ShortestAlts ¶

```
type ShortestAlts struct {
// contains filtered or unexported fields
}
```

ShortestAlts is a shortest-path tree created by the BellmanFordAllFrom or DijkstraAllFrom single-source shortest path functions.

#### func BellmanFordAllFrom ¶

BellmanFordAllFrom returns a shortest-path tree for shortest paths from u to all nodes in the graph g, or false indicating that a negative cycle exists in the graph. If the graph does not implement Weighted, UniformCost is used.

If g is a graph.Graph, all nodes of the graph will be stored in the shortest-path tree, otherwise only nodes reachable from u will be stored.

The time complexity of BellmanFordAllFrom is O(|V|.|E|).

#### func DijkstraAllFrom ¶

func DijkstraAllFrom(u graph.Node, g traverse.Graph) ShortestAlts

DijkstraAllFrom returns a shortest-path tree for shortest paths from u to all nodes in the graph g. If the graph does not implement Weighted, UniformCost is used. DijkstraAllFrom will panic if g has a u-reachable negative edge weight.

The time complexity of DijkstraAllFrom is O(|E|.log|V|).

#### func (ShortestAlts) AllTo ¶

func (p ShortestAlts) AllTo(vid int64) (paths [][]graph.Node, weight float64)

AllTo returns all shortest paths 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 (ShortestAlts) AllToFunc ¶

func (p ShortestAlts) AllToFunc(vid int64, fn func(path []graph.Node))

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 (ShortestAlts) From ¶

func (p ShortestAlts) From() graph.Node

From returns the starting node of the paths held by the ShortestAlts.

#### func (ShortestAlts) To ¶

To returns a shortest path to v and the weight of the path. If more than one shortest path exists between u and v, a randomly chosen path will be returned and unique is returned false. If a cycle with zero weight exists in the path, it will not be included, but unique will be returned false. If the path to v includes a negative cycle, one pass through the cycle will be included in path, but any path leading into the negative cycle will be lost, and weight will be returned as -Inf.

#### func (ShortestAlts) WeightTo ¶

func (p ShortestAlts) WeightTo(vid int64) float64

WeightTo returns the weight of the minimum path to v. If the path to v includes a negative cycle, the returned weight will not reflect the true path weight.

#### type UndirectedWeightLister ¶

type UndirectedWeightLister interface { graph.WeightedUndirected WeightedEdges() graph.WeightedEdges }

UndirectedWeightLister is an undirected graph that returns edge weights and the set of edges in the graph.

#### type Weighted ¶

type Weighted interface { // Weight returns the weight for the edge between // x and y with IDs xid and yid if Edge(xid, yid) // returns a non-nil Edge. // If x and y are the same node or there is no // joining edge between the two nodes the weight // value returned is implementation dependent. // Weight returns true if an edge exists between // x and y or if x and y have the same ID, false // otherwise. Weight(xid, yid int64) (w float64, ok bool) }

Weighted is a weighted graph. It is a subset of graph.Weighted.

#### type WeightedBuilder ¶

type WeightedBuilder interface { AddNode(graph.Node) SetWeightedEdge(graph.WeightedEdge) }

WeightedBuilder is a type that can add nodes and weighted edges.

#### type Weighting ¶

Weighting is a mapping between a pair of nodes and a weight. It follows the semantics of the Weighter interface.

#### func UniformCost ¶

UniformCost returns a Weighting that returns an edge cost of 1 for existing edges, zero for node identity and Inf for otherwise absent edges.

### Source Files ¶

a_star.go bellman_ford_moore.go dijkstra.go disjoint.go doc.go floydwarshall.go johnson_apsp.go shortest.go spanning_tree.go weight.go yen_ksp.go

### Directories ¶

Path | Synopsis |
---|---|

graph/path/dynamic | Package dynamic provides incremental heuristic graph path finding functions. |

graph/path/internal |

- Version
- v0.14.0 (latest)
- Published
- Aug 19, 2023
- Platform
- linux/amd64
- Imports
- 13 packages
- Last checked
- 4 hours ago –

Tools for package owners.