数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用Dijkstra算法实现Go语言程序，查找图中两节点间的最短路径
在这篇Go语言文章中，我们将探讨如何使用邻接矩阵和邻接表实现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("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算法，以使用两种不同的方法（邻接矩阵和邻接表）查找图中两个节点之间的最短路径。两种方法都运行良好，并各有优缺点。邻接矩阵方法简单易于实现，但对于较大的图需要更多的空间。邻接表方法更节省空间，可以处理更大的图，但是遍历每个顶点的邻居需要更多时间。
1K+ 次浏览
