資料結構
網路
關係資料庫管理系統(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+ 次瀏覽
