例題：到達(dá)目的地的方案數(shù)
題目鏈接：1976. 到達(dá)目的地的方案數(shù)文章來源：http://www.zghlxwxcb.cn/news/detail-842349.html
題目描述
文章來源地址http://www.zghlxwxcb.cn/news/detail-842349.html
代碼與解題思路
func countPaths(n int, roads [][]int) int {
g := make([][]int, n) // 構(gòu)建鄰接矩陣
for i, _ := range g {
g[i] = make([]int, n)
for j, _ := range g[i] {
g[i][j] = math.MaxInt / 2 // 到不了的地方就是無限大（初始化成這個值）
}
}
for _, v := range roads { // 無向圖
x, y, d := v[0], v[1], v[2]
g[x][y] = d
g[y][x] = d
}
dis := make([]int, n) // dis 數(shù)組存儲從起點(diǎn)到每個節(jié)點(diǎn)的當(dāng)前已知最短距離
for i := 1; i < n; i++ {
dis[i] = math.MaxInt / 2
}
f := make([]int, n) // 存儲到達(dá)每個節(jié)點(diǎn)的最短路徑數(shù)
f[0] = 1 // 到自己是一條
done := make([]bool, n) // 標(biāo)記每個節(jié)點(diǎn)是否被處理
for {
x := -1
for i, ok := range done {
// 找下一個未被處理的節(jié)點(diǎn)，x < 0 代表第一次進(jìn)去
// 而 x 代表的是未被處理過的節(jié)點(diǎn)中，到起點(diǎn)距離最短的節(jié)點(diǎn)
if ok == false && (x < 0 || dis[i] < dis[x]) {
x = i
}
}
if x == n-1 { // 走到第 n-1 個節(jié)點(diǎn)了
return f[n-1]
}
done[x] = true // 這個節(jié)點(diǎn)被處理了
// 遍歷從 x 出發(fā)能直接走到的所有下一個節(jié)點(diǎn)
// g[x] 的下標(biāo)是 y， 存的值是 d
for y, d := range g[x] {
newDis := dis[x] + d // 遍歷到到下一個節(jié)點(diǎn)的所有距離（當(dāng)前距離+每條路的邊權(quán)）
if newDis < dis[y] { // 找到了一條更短的路徑
dis[y] = newDis // 更新 dis[y]
f[y] = f[x] // 下一個節(jié)點(diǎn)就是 y，讓 f[y] 繼承前面的路徑數(shù)量
} else if newDis == dis[y] { // 又多了一條最短路徑
f[y] = (f[y] + f[x]) % 1_000_000_007 // 路徑的情況就多了 f[x] 種（可以畫圖理解）
}
}
}
}
構(gòu)建帶權(quán)無向圖的鄰接矩陣
g := make([][]int, n) // 構(gòu)建鄰接矩陣
for i, _ := range g {
g[i] = make([]int, n)
for j, _ := range g[i] {
g[i][j] = math.MaxInt / 2 // 到不了的地方就是無限大（初始化成這個值）
}
}
for _, v := range roads { // 無向圖
x, y, d := v[0], v[1], v[2]
g[x][y] = d
g[y][x] = d
}
到了這里，關(guān)于【圖論】Dijkstra 算法求最短路 - 構(gòu)建鄰接矩陣（帶權(quán)無向圖）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
