Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
1514. Path with Maximum Probability
Bookmark
Bellman-Ford
Dijkstra (Max-Heap)
Input
3 Nodes (A)
3 Nodes (B)
5 Nodes
Custom
n
=
3
,
edges
=
[[0,1],[1,2],[0,2]]
,
succProb
=
[0.5, 0.5, 0.2]
,
startNode
=
0
,
endNode
=
2
Success Probability Network
0.5
0.5
0.2
0
1
2
Edge List
0-1 0.5
1-2 0.5
0-2 0.2
prob
node 0
0.0
node 1
0.0
node 2
0.0
Success Probability Network
0.5
0.5
0.2
0
1
2
Edge List
0-1 0.5
1-2 0.5
0-2 0.2
prob
node 0
0.0
node 1
0.0
node 2
0.0
Success Probability Network
0.5
0.5
0.2
0
1
2
Edge 0-1 succeeds with probability 0.5
Edge List
0-1 0.5
1-2 0.5
0-2 0.2
prob
node 0
1.0
node 1
0.0
node 2
0.0
Success Probability Network
0.5
0.5
0.2
0
1
2
0.5 * 0.5 = 0.25 vs prob[0] = 1.0
Edge List
0-1 0.5
1-2 0.5
0-2 0.2
prob
node 0
1.0
node 1
0.5
node 2
0.0
Success Probability Network
0.5
0.5
0.2
0
1
2
0.5 * 0.5 = 0.25 vs prob[2] = 0.0
Edge List
0-1 0.5
1-2 0.5
0-2 0.2
prob
node 0
1.0
node 1
0.5
node 2
0.25
Success Probability Network
0.5
0.5
0.2
0
1
2
1.0 * 0.2 = 0.2 vs prob[2] = 0.25
Edge List
0-1 0.5
1-2 0.5
0-2 0.2
prob
node 0
1.0
node 1
0.5
node 2
0.25
Success Probability Network
0.5
0.5
0.2
0
1
2
Sweep 1 improved at least one node
Edge List
0-1 0.5
1-2 0.5
0-2 0.2
prob
node 0
1.0
node 1
0.5
node 2
0.25
Success Probability Network
0.5
0.5
0.2
0
1
2
1.0 * 0.5 = 0.5 vs prob[1] = 0.5
Edge List
0-1 0.5
1-2 0.5
0-2 0.2
prob
node 0
1.0
node 1
0.5
node 2
0.25
Success Probability Network
0.5
0.5
0.2
0
1
2
0.5 * 0.5 = 0.25 vs prob[2] = 0.25
Edge List
0-1 0.5
1-2 0.5
0-2 0.2
prob
node 0
1.0
node 1
0.5
node 2
0.25
Success Probability Network
0.5
0.5
0.2
0
1
2
1.0 * 0.2 = 0.2 vs prob[2] = 0.25
Edge List
0-1 0.5
1-2 0.5
0-2 0.2
prob
node 0
1.0
node 1
0.5
node 2
0.25
Success Probability Network
0.5
0.5
0.2
0
1
2
Best probability to 2 is 0.25
Edge List
0-1 0.5
1-2 0.5
0-2 0.2
prob
node 0
1.0
node 1
0.5
node 2
0.25
algo
master
.
io
Step:
3 nodes and 3 edges. Find the most likely path from 0 to 2.
0 / 26
Input
3 Nodes (A)
3 Nodes (B)
5 Nodes
Custom
n
=
3
,
edges
=
[[0,1],[1,2],[0,2]]
,
succProb
=
[0.5, 0.5, 0.2]
,
startNode
=
0
,
endNode
=
2
0 / 26
algo
master
.
io
Step:
3 nodes and 3 edges. Find the most likely path from 0 to 2.
