Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Number of Ways to Arrive at Destination
Bookmark
DFS Brute Force
Dijkstra
Input
Standard
Small
Diamond
Custom
n
=
7
,
roads
=
[[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
path
minDist =
∞
count =
0
count = 0
count the shortest paths from
0
to
6
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
path
minDist =
∞
count =
0
count = 0
count the shortest paths from
0
to
6
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
path
0
cost 0
minDist =
7
count =
1
count = 1
back at
0
: un-mark
6
so other paths can use it
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
path
0
→
1
→
2
cost 5
minDist =
7
count =
1
count = 1
edge
2 → 1
(weight 3):
8
already past the best 7, prune
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
path
0
→
1
→
2
→
5
→
3
cost 7
minDist =
7
count =
1
count = 1
edge
3 → 1
(weight 3):
10
already past the best 7, prune
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
path
0
→
1
→
2
→
5
cost 6
minDist =
7
count =
2
count = 2
back at
5
: un-mark
6
so other paths can use it
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
path
0
→
1
→
3
cost 5
minDist =
7
count =
2
count = 2
edge
3 → 1
(weight 3):
8
already past the best 7, prune
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
path
0
→
1
→
3
→
5
→
6
cost 7
minDist =
7
count =
2
count = 2
at node
6
, this path costs
7
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
path
0
→
1
→
3
→
5
→
2
cost 7
minDist =
7
count =
3
count = 3
edge
2 → 5
(weight 1):
8
already past the best 7, prune
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
current
path
0
→
4
cost 5
minDist =
7
count =
3
count = 3
edge
4 → 0
(weight 5):
10
already past the best 7, prune
7
2
3
3
3
1
1
1
5
2
0
1
2
3
4
5
6
start
dest
path
minDist =
7
count =
4
count = 4
4 shortest paths of length 7
algo
master
.
io
Step:
Count the shortest paths from node 0 to node 6
0 / 67
Input
Standard
Small
Diamond
Custom
n
=
7
,
roads
=
[[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
0 / 67
algo
master
.
io
Step:
Count the shortest paths from node 0 to node 6
