資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學使用Bellman-Ford演算法查詢加權有向無環圖中最長路徑的Go語言程式
在本文中，我們將編寫一個Go語言程式，使用Bellman-Ford演算法查詢加權有向無環圖中的最長路徑。Bellman-Ford演算法是一種常用的演算法，用於在加權有向圖中查詢從源頂點到其他頂點的最長路徑。
語法
func range(variable)
可以使用range函式迭代任何資料型別。這可以透過首先編寫range關鍵字，然後編寫我們想要迭代到的資料型別來實現。
func make ([] type, size, capacity)
在Go程式語言中建立陣列或對映時，make函式接收三個引數：要建立的變數型別、其大小和其容量。
演算法
步驟1 - 建立一個Edge結構體，包含三個欄位：src、dest和weight，型別均為int
步驟2 - 在此步驟中，建立一個find_longest_path函式，其輸入引數為edges、vertices和source
步驟3 - 此函式返回一個數組，該陣列描述從源頂點到所有其他頂點的最長路徑距離。
步驟4 - 在此步驟中，使用make作為內建函式建立一個名為dist的陣列來儲存路徑距離。
步驟5 - 最初，使用for迴圈，在每次迭代中將dist的元素設定為math.MinInt32並將源頂點設定為0。然後，使用巢狀迴圈在外迴圈中迭代vertices-1次。在內迴圈中，迭代edges陣列中的每個邊。
步驟6 - 對於每條邊，計算源頂點u、目標頂點v和權重w。然後，檢查到達源頂點u的距離是否不是math.MinInt32。
步驟7 - 然後檢視，如果到達u的距離與權重w的和大於當前到達v的距離，則將到達v的距離修改為到達u的距離與權重w的和。
步驟8 - dist陣列將儲存從源頂點到所有其他頂點的最長路徑距離。
步驟9 - 最後，在main函式中，建立頂點數和邊列表。
步驟10 - 在這裡，建立一個源頂點變數，用於查詢其最長路徑距離。然後，使用edges、vertices和source作為引數呼叫find_longest_path函式。獲得的結果將儲存在longest_path變數中。
步驟11 - 最後，使用for迴圈列印每個頂點的最長路徑距離，包括頂點索引和距離，並使用fmt包中的Println函式列印語句。
示例
Bellman-Ford演算法反覆鬆弛圖的邊並更新距離值，直到找到最佳最長路徑。
package main
import (
"fmt"
"math"
)
type Edge struct {
src, dest, weight int
}
func find_longest_path(edges []Edge, vertices, source int) []int {
dist := make([]int, vertices)
for i := range dist {
dist[i] = math.MinInt32
}
dist[source] = 0
for i := 0; i < vertices-1; i++ {
for _, edge := range edges {
u := edge.src
v := edge.dest
w := edge.weight
if dist[u] != math.MinInt32 && dist[u]+w > dist[v] {
dist[v] = dist[u] + w
}
}
}
return dist
}
func main() {
vertices := 6
edges := []Edge{
{0, 1, 5},
{0, 2, 3},
{1, 3, 6},
{1, 2, 2},
{2, 4, 4},
{2, 5, 2},
{2, 3, 7},
{3, 5, 1},
{3, 4, -1},
{4, 5, -2},
}
source := 1
longest_path := find_longest_path(edges, vertices, source)
fmt.Println("Longest path distances from source vertex", source, "to all other vertices:")
for I, dist := range longest_path {
fmt.Println("Vertex", I, ":", dist)
}
}
輸出
Longest path distances from source vertex 1 to all other vertices: Vertex 0 : -2147483648 Vertex 1 : 0 Vertex 2 : 2 Vertex 3 : 9 Vertex 4 : 8 Vertex 5 : 10
結論
在本文中，我們探討了使用Bellman-Ford演算法查詢加權有向無環圖中最長路徑的程式。需要注意的是，Bellman-Ford演算法的時間複雜度為O(V*E)，其中E和V分別表示邊數和頂點數。
384 次瀏覽
