package main
import (
	"fmt"
	"math"
)
// Dijkstra 算法用于計算無向圖的最短路徑
func dijkstra(graph [][]int, startNode int) []int {
	// 獲取節(jié)點數(shù)
	nodesCount := len(graph)
	// 初始化 visited 和 distance 數(shù)組
	visited := make([]bool, nodesCount)
	distance := make([]int, nodesCount)
	for i := 0; i < nodesCount; i++ {
		visited[i] = false
		distance[i] = math.MaxInt32 // 賦初值為最大值
	}
	// 起始節(jié)點到自身的距離為 0
	distance[startNode] = 0
	// 計算從起始節(jié)點到所有其他節(jié)點的最短距離
	for i := 0; i < nodesCount-1; i++ {
		minDistance := math.MaxInt32 // 最短距離的初始值為最大值
		currentNode := -1
		// 找到距離起始節(jié)點最近的未訪問節(jié)點
		for j := 0; j < nodesCount; j++ {
			if !visited[j] && distance[j] < minDistance {
				minDistance = distance[j]
				currentNode = j
			}
		}
		// 如果沒有找到最近的未訪問節(jié)點，則退出循環(huán)
		if currentNode == -1 {
			break
		}
		// 標記當前節(jié)點為已訪問
		visited[currentNode] = true
		// 更新起始節(jié)點到其他節(jié)點的距離
		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() {
	// 初始化無向圖
	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 // 起始節(jié)點為 0
	distances := dijkstra(graph, startNode)
	// 輸出起始節(jié)點到其他節(jié)點的最短距離
	fmt.Println("Shortest distances from node", startNode, "to all other nodes:")
	for i, d := range distances {
		fmt.Printf("Node %d: %d\n", i, d)
	}
}