Golang 使用 dijikstra 算法在图中查找所有节点对之间的最短路径

在这篇 Golang 程序文章中，我们将学习如何使用 struct 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]]