1. Detailed explanation of the implementation process
The Dijkstra algorithm is an algorithm used to calculate the shortest path of an undirected graph. It is based on a greedy strategy, each time the unvisited node that is currently closest to the starting node is selected for access, and the distance value of its neighbor node is updated to get the shortest path.
When implementing the Dijkstra algorithm, you need to follow the following steps:
1. Initialize the visited and distance arrays
First, you need to define two arrays visited and distance. Visited array is used to record whether a node has been accessed, and distance array is used to record the shortest distance from the starting node to each node.
In the specific implementation, it is necessary to traverse the entire node collection, initialize the visited array to false, and initialize the distance array to a sufficiently large value (for example, math.MaxInt32).
2. The distance from the starting node to itself is 0
The distance from the starting node to itself is 0, and the distance value of the starting node in the distance array needs to be assigned to 0.
3. Calculate the shortest distance from the starting node to all other nodes
The following operations are required in the loop:
- Found the closest unvisited node to the starting node
In the specific implementation, you can traverse the entire node collection, find the node closest to the starting node in the unvisited node, and mark it as the current node.
- Mark the current node as accessed
The current node needs to be marked as accessed and its visited array value is set to true.
- Update the distance from the starting node to other nodes
It is necessary to traverse the adjacent node of the current node, calculate the distance from the starting node to the node, and update the distance value of the node in the distance array. If the calculated distance value is smaller than the distance value of the node in the current distance array, update to this value.
This loop will be executed until all nodes are accessed, or the unreached node closest to the starting node cannot be found.
4. Return distance array
After the algorithm is executed, it is necessary to return the distance array, where distance[i] represents the shortest distance from the starting node to the node i.
2. Complete code implementation
package main
import (
"fmt"
"math"
)
// Dijkstra algorithm is used to calculate the shortest path of an undirected graphfunc dijkstra(graph [][]int, startNode int) []int {
// Get the number of nodes nodesCount := len(graph)
// Initialize the visited and distance arrays visited := make([]bool, nodesCount)
distance := make([]int, nodesCount)
for i := 0; i < nodesCount; i++ {
visited[i] = false
distance[i] = math.MaxInt32 // Assign the initial value to the maximum value }
// The distance from the starting node to itself is 0 distance[startNode] = 0
// Calculate the shortest distance from the starting node to all other nodes for i := 0; i < nodesCount-1; i++ {
minDistance := math.MaxInt32 // The initial value of the shortest distance is the maximum value currentNode := -1
// Find the nearest unvisited node to the starting node for j := 0; j < nodesCount; j++ {
if !visited[j] && distance[j] < minDistance {
minDistance = distance[j]
currentNode = j
}
}
// If the nearest unvisited node is not found, the loop is exited if currentNode == -1 {
break
}
// Mark the current node as accessed visited[currentNode] = true
// Update the distance from the starting node to other nodes for j := 0; j < nodesCount; j++ {
if graph[currentNode][j] != -1 {
newDistance := distance[currentNode] + graph[currentNode][j]
if newDistance < distance[j] {
distance[j] = newDistance
}
}
}
}
return distance
}
func main() {
// Initialize the undirected graph graph := [][]int{
{-1, 2, -1, 6, -1},
{2, -1, 3, 8, 5},
{-1, 3, -1, -1, 7},
{6, 8, -1, -1, 9},
{-1, 5, 7, 9, -1},
}
startNode := 0 // The starting node is 0 distances := dijkstra(graph, startNode)
// Output the shortest distance from the starting node to other nodes ("Shortest distances from node", startNode, "to all other nodes:")
for i, d := range distances {
("Node %d: %d\n", i, d)
}
}This program implements a simple Dijkstra algorithm to calculate the shortest path for a given undirected graph. It represents the connectivity and distance between nodes in the graph through a two-dimensional array graph. graph[i][j] represents the distance between nodes i and j, and if there are no edges connected between them, the value is -1. The program then calls the dijkstra function to calculate the shortest distance from the specified starting node to all other nodes and outputs the result to the console.
This is all about this article about Golang implementing the Dijkstra algorithm. For more related content of golang Dijkstra algorithm, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!