package main
import (
"fmt"
"strconv"
)
const N int = 4
const INF int = 501
var g [N][N][2]int
var dis [N 1]int
var pay [N]int
var known [N]bool
var n, m, s, d, i, j, t1, t2, v int
var path map[int][]int
func findMinDistance() {
disMin := INF
for i := 0; i < n; i {
if !known[i] && dis[i] < disMin {
v = i
disMin = dis[i]
}
}
}
func dijkstra() {
for k := 1; k < n; k {
findMinDistance() //先把状态为unknown的节点中到起点距离最短的点
//接下来按照之前介绍的算法使用距离最短的节点对其它节点进行优化
known[v] = true
for i = 0; i < n; i {
if !known[i] && g[v][i][0] < INF {
if dis[v] g[v][i][0] < dis[i] {
dis[i] = dis[v] g[v][i][0]
pay[i] = pay[v] g[v][i][1]
footPrint := path[v]
path[i] = append(footPrint, v)
} else if !known[i] && dis[v] g[v][i][0] == dis[i] && pay[v] g[v][i][1] < pay[i] {
pay[i] = pay[v] g[v][i][1]
}
}
}
}
}
func main() {
//以下是初始化城市个数、高速公路条数、起始城市、终点城市的工作
path = make(map[int][]int)
n = 4
m = 5
s = 0
d = 3
//初始化时先把path对应的路径置为空
for i := 0; i < n; i {
s1 := make([]int, 0)
path[i] = s1
}
//初始化化时先把g数组对应的路径置为空
for i = 0; i < n; i {
for j := 0; j < n; j {
g[i][j][0] = INF
g[i][j][1] = INF
}
}
keyInput := [...][6]int{{0, 1, 1, 20}, {1, 2, 3, 30}, {0, 3, 40, 10}, {0, 2, 10, 20}, {2, 3, 2, 20}, {1, 3, 6, 20}}
//把道路信息写入g数组
for ; m > 0; m-- {
i = keyInput[m-1][0]
j = keyInput[m-1][1]
t1 = keyInput[m-1][2]
t2 = keyInput[m-1][3]
g[i][j][0] = t1
g[j][i][0] = t1
g[i][j][1] = t2
g[j][i][1] = t2
}
//fmt.Println(g)
//初始化known数组全部置为false状态
for i = 0; i < N; i {
known[i] = false
}
//初始化起点到编号为j节点的距离及花费信息
for j = 0; j < n; j {
dis[j] = g[s][j][0]
pay[j] = g[s][j][1]
}
dis[s] = 0
pay[s] = 0
dis[n] = INF
dijkstra() //调用dijkstra算法
if dis[d] < INF {
fmt.Println("Distance is " strconv.Itoa(dis[d]) ",The cost is " strconv.Itoa(pay[d]))
fmt.Println("Path is", path[d])
}
}
