1514. Path with Maximum Probability
給一個無向圖有N個節點
再給edges矩陣代表兩個節點有邊存在
succProb[i]則是表示edges[i]成功度過的可能性
給你start、end節點
請回傳從start成功到end的最大可能性
如果沒有可以可以從start到end的路徑則回傳0
思路:
用Dijkstra's algorithm
我原本以為Dijkstra只能用在求最短路徑
所以一開始是把succProb取對數再乘以-1
這樣就可以變成最短路徑問題了
不過看了答案不用這麼麻煩，就照題目原本的思路走了
太久沒寫Dijkstra's algorithm寫的時候很卡
稍微介紹一下，當作複習，用最短距離來解釋
在求兩點間的最小值時，可以分成已經到達和還沒到達的兩個團體
用visited、distance紀錄到達過的節點和到各節點的最短距離
startnode的距離是0，所以一開始會先到startnode
接著就從startnode能到達的節點中，選離已到達group距離最短的節點當從下一個節點
把這個節點放到已到達的group
在這個過程要更新到達每個節點離已到達group的最短距離
這樣更新到最後，就可以求出startnode到每個節點的最短距離
然後這題要配合heap，不然記憶體會爆
golang code :
type Edges struct {
next_node int
distance float64
}
type Vertex struct {
node int
distance float64
}
type max_heap []*Vertex
func (this max_heap) Len() int { return len(this) }
func (this max_heap) Less(i, j int) bool { return this[i].distance > this[j].
distance }
func (this max_heap) Swap(i, j int) { this[i], this[j] = this[j], this[i]
}
func (this *max_heap) Push(x any) {
*this = append(*this, x.(*Vertex))
}
func (this *max_heap) Pop() any {
n := len(*this)
res := (*this)[n-1]
(*this) = (*this)[:n-1]
return res
}
func maxProbability(n int, edges [][]int, succProb []float64, start_node int,
end_node int) float64 {
rec := make([][]Edges, n)
for i := 0; i < n; i++ {
rec[i] = []Edges{}
}
for key, val := range edges {
a, b, c := val[0], val[1], succProb[key]
rec[a] = append(rec[a], Edges{b, c})
rec[b] = append(rec[b], Edges{a, c})
}
visit := make([]bool, n)
distance := make([]float64, n)
var maxheap max_heap
heap.Push(&maxheap, &Vertex{start_node, 1})
for maxheap.Len() > 0 {
cur := heap.Pop(&maxheap).(*Vertex)
if visit[cur.node] {
continue
}
if cur.node == end_node {
return distance[end_node]
}
visit[cur.node] = true
for _, val := range rec[cur.node] {
new_distance := val.distance * cur.distance
if new_distance > distance[val.next_node] {
distance[val.next_node] = new_distance
heap.Push(&maxheap, &Vertex{val.next_node, new_distance})
}
}
}
return 0.0
}