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
}