Golang程序实现Dijkstra算法来查找图中两个节点之间的最短路径

在这篇Golang文章中，我们将探讨如何使用邻接矩阵以及邻接列表来实现Dijkstra算法来查找图中两个节点之间的最短路径。Dijkstra算法用于解决具有非负边权的图中的单源最短路径问题。

算法

步骤1 - 首先，我们需要导入fmt和math包。然后创建长度为n的dist数组（图中节点的数量），并用math.MaxInt32进行初始化。此数组将存储从起始节点到图中每个其他节点的最短距离。
步骤2 - 然后创建一个名为dijikastra的函数，该函数接受图表和两个整数作为参数。
步骤3 - 在函数内部创建一个长度为n的visited数组，并将其初始化为false。此数组将跟踪已经访问过的节点。
步骤4 - 将dist [start]设置为0，其中start是起始节点的索引。重复以下n-1次。
步骤5 - 查找尚未访问但距离起始节点最短的节点u（即dist [u]是尚未访问的所有节点中最小的）。将u标记为已访问。
步骤6 - 对于u的每个邻居v，如果dist [u] + graph [u] [v]小于当前的dist [v]，则更新dist [v]为dist [u] + graph [u] [v]。然后返回dist数组。
步骤7 - 这里，graph是图的邻接矩阵，其中graph [i] [j]表示从节点i到节点j的边的权重。如果节点i和节点j之间没有边，则graph [i] [j]应为0。

示例1

邻接矩阵是一个用于表示图的二维数组，其中行和列表示顶点，值表示它们之间的边的权重。要使用邻接矩阵实现Dijkstra算法，我们可以创建一个二维数组，然后将距离初始化为无限制，然后遍历顶点。

package main

import (
   "fmt"
   "math"
)

func dijkstra(graph [][]int, start int, end int) []int {
   n := len(graph)
   dist := make([]int, n)
   visited := make([]bool, n)

   for i := 0; i < n; i++ {
      dist[i] = math.MaxInt32
      visited[i] = false
   }

   dist[start] = 0

   for count := 0; count < n-1; count++ {
      u := -1

      for i := 0; i < n; i++ {
         if !visited[i] && (u == -1 || dist[i] < dist[u]) {
            u = i
         }
      }

      if u == -1 {
         break
      }

      visited[u] = true

      for v := 0; v < n;v++ {
         if graph[u][v] != 0 && dist[u]+graph[u][v] < dist[v] {
            dist[v] = dist[u] + graph[u][v]
         }
      }
   }

   return dist
}

func main() {
   graph := [][]int{
      {0, 5, 0, 9, 0},
      {5, 0, 2, 0, 0},
      {0, 2, 0, 3, 7},
      {9, 0, 3, 0, 0},
      {0, 0, 7, 0, 0},
   }
   fmt.Println("给定的节点是：", graph)
   start := 0
   end := 4

   dist := dijkstra(graph, start, end)

   fmt.Printf("从节点%d到节点%d的最短路径：%d\n", start, end, dist[end])
}

输出

给定的节点是：[[0 5 0 9 0] [5 0 2 0 0] [0 2 0 3 7] [9 0 3 0 0] [0 0 7 0 0]]
从节点0到节点4的最短路径：14

示例2

邻接表是一种用于表示图的数据结构，在这种数据结构中每个顶点都与其相邻顶点列表相关联。为了使用邻接表实现Dijkstra算法，我们可以创建一个映射，其中键是顶点，值是其相邻顶点及其权重的切片。

package main

import (
   "container/heap"
   "fmt"
   "math"
)

type node struct {
   index int
   dist  int
}

type priorityQueue []*node

func (pq priorityQueue) Len() int {
   return len(pq)
}

func (pq priorityQueue) Less(i, j int) bool {
   return pq[i].dist < pq[j].dist
}

func (pq priorityQueue) Swap(i, j int) {
   pq[i], pq[j] = pq[j], pq[i]
}

func (pq *priorityQueue) Push(x interface{}) {
   *pq = append(*pq, x.(*node))
}

func (pq *priorityQueue) Pop() interface{} {
   old := *pq
   n := len(old)
   x := old[n-1]
   *pq = old[0 : n-1]
   return x
}

func dijkstra(graph [][]node, start int, end int) []int {
   n := len(graph)
   dist := make([]int, n)
   visited := make([]bool, n)

   for i := 0; i < n; i++ {
      dist[i] = math.MaxInt32
      visited[i] = false
   }

   dist[start] = 0

   pq := make(priorityQueue, 0)
   heap.Push(&pq, &node{start, 0})

   for pq.Len() > 0 {
      u := heap.Pop(&pq).(*node)

      if visited[u.index] {
         continue
      }

      visited[u.index] = true

      for _, v := range graph[u.index] {
         if !visited[v.index] && dist[u.index]+v.dist < dist[v.index] {
            dist[v.index] = dist[u.index] + v.dist
            heap.Push(&pq, &node{v.index, dist[v.index]})
         }
      }
   }

   return dist
}

func main() {
   graph := [][]node{
      {{1, 5}, {3, 9}},
      {{0, 5}, {2, 2}},
      {{1, 2}, {3, 3}, {4, 7}},
      {{0, 9}, {2, 3}},
      {{2, 7}},
   }
   fmt.Println("给定的节点为：", graph)
   start := 0
   end := 4
   dist := dijkstra(graph, start, end)
   fmt.Printf("从节点 %d 到 %d 的最短路径为：%d\n", start, end, dist[end])
}

输出

给定的节点为： [[{1 5} {3 9}] [{0 5} {2 2}] [{1 2} {3 3} {4 7}] [{0 9} {2 3}] [{2 7}]]
从节点 0 到 4 的最短路径为：14

结论

在本文中，我们探讨了如何在Go中使用邻接矩阵和邻接表两种不同的方法实现Dijkstra算法，以在图形中找到两个节点之间的最短路径。两种方法都能很好地工作，并且各自都有优点和缺点。邻接矩阵方法简单易用，但对于更大的图形需要更多的空间。邻接表方法空间效率更高，可以处理更大的图形，但需要更多时间来遍历每个顶点的邻居。