Skip to content

Commit ec20f7c

Browse files
wisdompeakwisdompeak
authored
Update Readme.md
1 parent c064a91 commit ec20f7c

File tree

1 file changed

+3
-1
lines changed
  • Graph/1514.Path-with-Maximum-Probability

1 file changed

+3
-1
lines changed

‎Graph/1514.Path-with-Maximum-Probability/Readme.md‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,8 @@
88

99
本题需要改造一番才能使用Dijkstra算法。原本的题意是求最大乘积路径问题：
1010
```
11-
maxmize prob(E1)*prob(E2)*...*prob(Ek) = maxmize log[prob(E1)]+log[prob(E2)] + ... + log[prob(Ek)] = minimize -log[prob(E1)] -log[prob(E2)] - ... -log[prob(Ek)]
11+
maxmize prob(E1)*prob(E2)*...*prob(Ek)
12+
= maxmize log[prob(E1)]+log[prob(E2)] + ... + log[prob(Ek)]
13+
= minimize -log[prob(E1)] -log[prob(E2)] - ... -log[prob(Ek)]
1214
```
1315
我们发现每条边的-log[prob(Ek)]都是正数，并且目标是最小化路径之和。所以考虑-log[prob(Ek)]为权重的图，原题就可以转化成标准的最短路径问题。

0 commit comments

Comments
 (0)