极客笔记Golang 实现Dijkstra算法在图中查找两个节点之间的最短路径
在这篇Golang文章中，我们将探索如何使用邻接矩阵和邻接表来实现Dijkstra算法，在图中查找两个节点之间的最短路径。Dijkstra算法用于解决带有非负边权的图的单源最短路径问题。
步骤
- 步骤 1 - 首先，我们需要导入fmt和math包。然后创建一个长度为n（图中节点的数量）的dist数组，并将其初始化为math.MaxInt32。这个数组将存储从起始节点到图中其他每个节点的最短距离。
-
步骤 2 - 然后创建一个名为dijkistra的函数，它接受图和两个整数作为参数。
-
步骤 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("The given nodes are:", graph)
start := 0
end := 4
dist := dijkstra(graph, start, end)
fmt.Printf("Shortest path from node %d to %d: %d\n", start, end, dist[end])
}
输出
The given nodes are: [[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]]
Shortest path from node 0 to 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("The given nodes are:", graph)
start := 0
end := 4
dist := dijkstra(graph, start, end)
fmt.Printf("Shortest path from node %d to %d: %d\n", start, end, dist[end])
}
输出
The given nodes are: [[{1 5} {3 9}] [{0 5} {2 2}] [{1 2} {3 3} {4 7}] [{0 9} {2 3}] [{2 7}]]
Shortest path from node 0 to 4: 14
结论
在本文中，我们探讨了如何使用两种不同的方法（邻接矩阵和邻接表）在Go语言中实现Dijkstra算法来找到图中两个节点之间的最短路径。这两种方法都能很好地工作，并且各自都有优缺点。邻接矩阵方法简单易用，但对于较大的图需要更多的空间。邻接表方法更节省空间，可以处理更大的图，但需要更长的时间来遍历每个顶点的相邻结点。