資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 Bellman-Ford 演算法查詢從源節點到目標節點的最短路徑的 Golang 程式
Bellman-ford 演算法用於在加權有向圖中查詢從源節點到其他節點的最短距離。此演算法還可以預測圖中的負權環。它的時間複雜度為 O(V*E)，其中 V 代表頂點，E 代表邊。在這篇 Golang 文章中，我們將編寫程式以使用 Bellman-ford 演算法查詢從源節點到目標節點的最短路徑。
語法
func range(variable)
range 函式迭代任何資料型別。要利用它，首先鍵入 range 關鍵字，後跟我們要迭代到的資料型別，迴圈將一直迭代到變數的最後一個元素。make([] 型別, 大小, 容量)
func make ([] type, size, capacity)
Go 中的 make 函式用於構建陣列/對映。它接收要生成的變數的型別以及其大小和容量作為引數。
演算法
步驟 1 - 建立距離陣列。
步驟 2 - 重複放鬆邊界
步驟 3 - 檢查負權環。
步驟 4 - 查詢最短距離。
步驟 5 - 確定最短距離。
示例
在此示例中，我們將編寫一個 Go 語言程式，以藉助名為 Bellman-ford 演算法的最短路徑查詢演算法，查詢從源節點到目標節點的最短路徑。
package main
import (
"fmt"
"math"
)
type Edge struct {
source, target, weight int
}
func Bellman_ford(edges []Edge, num_vertices, source int, target int) ([]int, error) {
distances := make([]int, num_vertices)
for i := range distances {
distances[i] = math.MaxInt32
}
distances[source] = 0
for i := 0; i < num_vertices-1; i++ {
for _, edge := range edges {
if distances[edge.source]+edge.weight < distances[edge.target] {
distances[edge.target] = distances[edge.source] + edge.weight
}
}
}
for _, edge := range edges {
if distances[edge.source]+edge.weight < distances[edge.target] {
return nil, fmt.Errorf("graph contains negative-weight cycle")
}
}
return distances, nil
}
func main() {
edges := []Edge{
{0, 1, 4},
{0, 2, 3},
{1, 3, 2},
{1, 4, 3},
{1, 2, 1},
{2, 1, 1},
{2, 3, 4},
{2, 4, 5},
{4, 3, 2},
}
num_vertices := 5
source := 0
target := 3
distances, err := Bellman_ford(edges, num_vertices, source, target)
if err != nil {
fmt.Println("Error:", err)
return
}
fmt.Println("Shortest distances from source to all vertices:")
for i, distance := range distances {
fmt.Printf("Vertex %d: %d\n", i, distance)
}
fmt.Printf("Shortest distance from source to target (vertex %d to vertex %d): %d\n", source, target, distances[target])
}
輸出
Shortest distances from source to all vertices: Vertex 0: 0 Vertex 1: 4 Vertex 2: 3 Vertex 3: 6 Vertex 4: 7 Shortest distance from source to target (vertex 0 to vertex 3): 6
結論
在本文中，我們探討了一個使用 Bellman-ford 演算法查詢從源頂點到目標節點的最短路徑的程式。該方法簡單直接，可以根據手頭問題的需求隨時使用。
更新於: 2023年7月6日
159 次檢視
廣告