使用 Dijkstra 演算法查詢圖中所有節點對之間最短路徑的 Golang 程式

在這篇 Golang 程式文章中，我們將學習如何使用結構體 Edge 來表示圖中的加權邊，以及 dijkstra 函式如何接收節點數 n 和 Edge 物件切片作為輸入。它返回一個二維切片，表示圖中所有節點對之間的距離矩陣。

在這篇 Golang 文章中，我們將探討如何在圖中實現 Dijkstra 演算法以查詢所有節點對之間的最短路徑。

演算法

  • 步驟 1 − 首先，我們需要匯入 fmt 和 math 包。然後定義一個 Edge 結構體來表示圖中的加權邊，其欄位包括起始節點、結束節點和邊權重。

  • 步驟 2 − 定義一個函式 dijkstra(n int, edges []Edge) [][]int，該函式接收節點數 n 和 Edge 物件切片作為輸入，並返回一個二維切片，表示圖中所有節點對之間的距離矩陣。

  • 步驟 3 − 初始化一個大小為 n x n 的鄰接矩陣 adj，並將所有條目設定為無窮大，除了對角線條目，這些條目設定為 0。根據輸入切片中的邊填充鄰接矩陣。

  • 步驟 4 − 初始化一個大小為 n x n 的距離矩陣 dist，並將鄰接矩陣中的值複製到其中。

  • 步驟 5 − 使用三個巢狀迴圈計算所有節點對之間的最短路徑。外迴圈遍歷所有節點 k，內迴圈遍歷所有節點對 i 和 j。

  • 步驟 6 − 對於每一對節點，檢查從 i 到 k 的距離加上從 k 到 j 的距離是否小於從 i 到 j 的當前距離。如果是，則使用新的最短路徑距離更新距離矩陣，並返回距離矩陣。

  • 步驟 7 − 現在，開始 main() 函式。在 main() 中，透過將圖的邊作為值傳遞給它來初始化一個數組。

  • 步驟 8 − 然後呼叫 dijkastra() 函式，並將上面初始化的陣列作為引數傳遞給該函式，並將獲得的結果儲存在一個變數中。

  • 步驟 9 − 最後列印獲得的結果，即圖中所有節點對之間的最短路徑。

示例

以下示例表示圖中所有節點對之間的距離矩陣，其中 dist[i][j] 表示從節點 i 到節點 j 的最短路徑距離。例如，dist[0][1] 為 5，這意味著從節點 0 到節點 1 的最短路徑權重為 5。類似地，dist[2][3] 為 1，這意味著從節點 2 到節點 3 的最短路徑權重為 1。

package main

import (
   "fmt"
   "math"
)

type Edge struct {
   from int
   to   int
   cost int
}

func dijkstra(n int, edges []Edge) [][]int {
   // Initialize adjacency matrix
   adj := make([][]int, n)
   for i := 0; i < n; i++ {
      adj[i] = make([]int, n)
      for j := 0; j < n; j++ {
         if i == j {
            adj[i][j] = 0
         } else {
            adj[i][j] = math.MaxInt32
         }
      }
   }

   // Build adjacency matrix
   for _, e := range edges {
      adj[e.from][e.to] = e.cost
   }

   // Initialize distance matrix
   dist := make([][]int, n)
   for i := 0; i < n; i++ {
      dist[i] = make([]int, n)
      copy(dist[i], adj[i])
   }

   // Compute shortest path between all pairs
   for k := 0; k < n; k++ {
      for i := 0; i < n; i++ {
         for j := 0; j < n; j++ {
            if dist[i][k]+dist[k][j] < dist[i][j] {
               dist[i][j] = dist[i][k] + dist[k][j]
            }
         }
      }
   }
   return dist
}

func main() {
   n := 4
   edges := []Edge{
      {0, 1, 5},
      {0, 2, 10},
      {1, 2, 3},
      {2, 3, 1},
      {3, 0, 2},
   }
   fmt.Println("The given vertices of graph are:", edges)
   dist := dijkstra(n, edges)
   fmt.Println("The shortest distance between all pairs of nodes are:", dist)
}

輸出

The given vertices of graph are: [{0 1 5} {0 2 10} {1 2 3} {2 3 1} {3 0 2}]
The shortest distance between all pairs of nodes are: [[0 5 8 9] [6 0 3 4] [3 8 0 1] [2 7 10 0]]

結論

我們已經成功編譯並執行了一個 Go 語言程式，使用 Dijkstra 演算法查詢圖中所有節點對之間的最短路徑。Dijkstra 演算法是計算圖中最短路徑的強大工具，本文中提供的 Go 實現提供了一種清晰簡單的方法來應用該演算法以查詢圖中所有節點對之間的最短路徑。

更新於: 2023年4月5日

477 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告