Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Shortest Path Visiting All Nodes
Bookmark
Backtracking
Bitmask BFS
Bitmask DP
Input
Standard
Small
Triangle
Custom
graph
=
[[1,2,3],[0],[0],[0]]
0
1
2
3
walk: 0 edges, best 6
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
walk
0
1
2
3
walk: 0 edges, best 6
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
walk
0
1
2
3
walk: 6 edges, best 6
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
walk
0
→
1
→
0
→
1
→
0
→
2
→
0
6 edges vs best
6
prune this walk
0
1
2
3
walk: 4 edges, best 6
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
walk
0
→
1
→
0
→
2
→
0
edge
0 → 3
step onto it
0
1
2
3
walk: 2 edges, best 5
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
walk
0
→
2
→
0
2 edges vs best
5
keep walking
0
1
2
3
walk: 4 edges, best 5
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
walk
0
→
2
→
0
→
2
→
0
edge
0 → 1
un-marked again
0
1
2
3
walk: 1 edge, best 5
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
walk
0
→
3
1 edges vs best
5
keep walking
0
1
2
3
walk: 4 edges, best 5
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
walk
0
→
3
→
0
→
2
→
0
edge
0 → 1
step onto it
0
1
2
3
walk: 0 edges, best 5
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
walk
0
edge
0 → 3
un-marked again
0
1
2
3
walk: 4 edges, best 5
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
walk
1
→
0
→
1
→
0
→
3
walk
1 → 0 → 1 → 0 → 3
4 edges
0
1
2
3
answer
answer = 4
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
walk
shortest path visiting all nodes = 4
algo
master
.
io
Step:
Walk every route through all 4 nodes and keep the shortest
0 / 320
Input
Standard
Small
Triangle
Custom
graph
=
[[1,2,3],[0],[0],[0]]
0 / 320
algo
master
.
io
Step:
Walk every route through all 4 nodes and keep the shortest
