資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 Golang 實現 Bellman-Ford 演算法的程式
Bellman-Ford 演算法是一種圖遍歷方法，用於在加權網路中查詢從特定頂點到所有頂點的最短距離。在本文中，我們將編寫一個 Go 語言程式來實現 Bellman-Ford 演算法。此演算法用於處理需要在加權有向圖中查詢從源頂點到其他頂點的最短路徑的情況。它透過在找到最短路徑時更新頂點的距離值來工作。
語法
func make ([] type, size, capacity)
Go 語言中的 **make** 函式用於建立陣列/對映，它接受要建立的變數型別、其大小和容量作為引數。
func append(slice, element_1, element_2…, element_N) []T
append 函式用於向陣列切片新增值。它接受多個引數。第一個引數是要新增值的陣列，後跟要新增的值。然後，該函式返回包含所有值的最終陣列切片。
func len(v Type) int
len() 函式用於獲取任何引數的長度。它將要查詢長度的資料型別變數作為引數，並返回表示變數長度的整數值。
演算法
**步驟 1** - 建立一個 Edge 結構體來表示圖中的邊，它包含三個欄位：源 (source，型別為 int)，目標 (destination，型別為 int) 和權重 (weight，型別為 float)。
**步驟 2** - 然後，建立一個 Graph 結構體來表示加權有向圖，它包含兩個欄位：頂點數 (number of vertices，型別為 int) 和邊切片 (edges)。
**步驟 3** - 建立一個 BellmanFord() 函式，它以圖和源頂點作為輸入，並返回距離陣列和前驅頂點陣列。
**步驟 4** - 然後，初始化所有頂點的距離陣列 (dist[]) 和前驅頂點陣列 (prev[])。檢查是否存在負權迴路，即 dist[u] + w 是否小於 dist[v]。
**步驟 5** - 建立一個 PrintShortestPaths() 函式，它列印從源頂點到所有其他頂點的最短路徑。
**步驟 6** - 然後，透過遍歷從起始點開始的前驅頂點陣列來構造最短路徑，並列印距離和路徑。建立 main 函式並初始化源頂點為 0。
**步驟 7** - 最後，執行 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]
結論
在本文中，我們使用結構體執行了實現 Bellman-Ford 演算法的程式。我們探討了此演算法的工作原理，還了解了如何使用鄰接表表示圖。
241 次檢視
