blob: 1fa04b1f8070353aca2f94c50611247a2ae220e0 [file] [log] [blame]
 // Copyright ©2017 The Gonum Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. package path_test import ( "fmt" "math" "gonum.org/v1/gonum/graph/path" "gonum.org/v1/gonum/graph/simple" ) func ExampleBellmanFordFrom_negativecycles() { // BellmanFordFrom can be used to find a non-exhaustive // set of negative cycles in a graph. Enumerating the // exhaustive list requires iterations of the procedure // here successively omitting links from the new node // to already found negative cycles. // 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. nodes := g.Nodes() for nodes.Next() { g.SetWeightedEdge(simple.WeightedEdge{F: simple.Node('Q'), T: nodes.Node()}) } // 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 _, n := range []simple.Node{'a', 'b', 'c', 'd', 'e', 'f'} { p, w := pt.To(n.ID()) if math.IsNaN(w) { fmt.Printf("negative cycle in path to %c path:%c\n", n, 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] }