Golang 实现Bellman-Ford算法

Bellman-Ford算法是一种图遍历方法，用于在加权网络中查找从一个特定顶点到所有顶点的最短距离。在本文中，我们将编写一个Go语言程序来实现Bellman-Ford算法。该算法用于处理需要在加权有向图中从源顶点到其他顶点找到最短路径的情况。如果找到最短路径，它会更新顶点的距离值。

语法

func make ([] type, size, capacity)

make 函数在Go语言中用于创建数组/映射，它接受要创建的变量类型、大小和容量作为参数。

func append(slice, element_1, element_2…, element_N) []T

append函数用于向数组中添加值。它接受多个参数。第一个参数是我们希望添加值的数组，接着是要添加的值。然后函数将返回包含所有值的最终数组切片。

func len(v Type) int

len() 函数用于获取任何参数的长度。它接受一个参数作为数据类型的变量，我们希望找到它的长度，并返回一个整数值，即变量的长度。

步骤

第一步 - 创建一个边缘结构来表示图中的一条边，它有三个字段：源（整型）、目标（整型）和权重（浮点型）。
第二步 - 然后，创建一个图结构来表示加权有向图，它有两个字段：顶点的数量（整型）和一组边。
第三步 - 创建一个 BellmanFord() 函数，它接受一个图和源顶点作为输入，并返回距离数组和前驱节点数组。
第四步 - 然后，初始化所有顶点的距离数组（dist[]）和前驱节点数组（prev[]）。检查 dist[u] + w 是否小于 dist[v]，以确定是否存在负权重环路。
第五步 - 创建一个 PrintShortestPaths() 函数，用于打印从源顶点到所有其他顶点的最短路径。
第六步 - 然后，通过遍历前驱节点数组构建最短路径，并打印距离和路径。创建一个 main 函数，并将源顶点初始化为 0。
第七步 - 最后，执行 Bellman-Ford 算法，获取距离数组和前驱节点数组，如果数组不为空，则打印从源顶点到最短路径。

示例

在本文中，我们将编写一个 Go 语言程序，实现 Bellman-Ford 算法，以在加权有向图中找到最短路径。

package main

import (
   "fmt"
   "math"
)
type Edge struct {
   src    int     
   dest   int     
   weight float64 
}
type Graph struct {
   vertices int   
   edges    []Edge 
}
func InitGraph(vertices int) *Graph {
   return &Graph{
      vertices: vertices,
      edges:    make([]Edge, 0),
   }
}
func (g *Graph) AddEdge(src, dest int, weight float64) {
   g.edges = append(g.edges, Edge{src, dest, weight})
}
func BellmanFord(g *Graph, source int) ([]float64, []int) {
   dist := make([]float64, g.vertices) 
   prev := make([]int, g.vertices)     
   for i := 0; i < g.vertices; i++ {
      dist[i] = math.Inf(1) 
      prev[i] = -1        
   }
   dist[source] = 0 

   for i := 1; i < g.vertices; i++ {
      for _, edge := range g.edges {
         u := edge.src
         v := edge.dest
         w := edge.weight
         if dist[u]+w < dist[v] {
            dist[v] = dist[u] + w
            prev[v] = u
         }
      }
   }

   for _, edge := range g.edges {
      u := edge.src
      v := edge.dest
      w := edge.weight
      if dist[u]+w < dist[v] {
         fmt.Println("Graph contains a negative weight cycle")
         return nil, nil
      }
   }

   return dist, prev
}

func PrintShortestPaths(dist []float64, prev []int, source int) {
   fmt.Println("Shortest Paths from vertex", source)
   for i := 0; i < len(dist); i++ {
      if dist[i] == math.Inf(1) {
         fmt.Printf("Vertex %d is not reachable\n", i)
      } else {
         path := []int{}
         j := i
         for j != -1 {
            path = append([]int{j}, path...)
            j = prev[j]
         }
         fmt.Printf("Vertex %d: Distance=%f, Path=%v\n", i, dist[i], path)
      }
   }
}

func main() {
   g := InitGraph(5)

   g.AddEdge(0, 1, 6)
   g.AddEdge(0, 2, 7)
   g.AddEdge(1, 2, 8)
   g.AddEdge(1, 3, -4)
   g.AddEdge(1, 4, 5)
   g.AddEdge(2, 3, 9)
   g.AddEdge(2, 4, -3)
   g.AddEdge(3, 1, 7)
   g.AddEdge(4, 0, 2)
   g.AddEdge(4, 3, 7)

   source := 0
   dist, prev := BellmanFord(g, source)
   if dist != nil && prev != nil {
      PrintShortestPaths(dist, prev, source)
   }
}

输出

Shortest Paths from vertex 0
Vertex 0: Distance=0.000000, Path=[0]
Vertex 1: Distance=6.000000, Path=[0 1]
Vertex 2: Distance=7.000000, Path=[0 2]
Vertex 3: Distance=2.000000, Path=[0 1 3]
Vertex 4: Distance=4.000000, Path=[0 2 4]