Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Shortest Path Visiting All Nodes
Bookmark
Input
Standard
Small
Triangle
Custom
graph
=
[[1,2,3],[0],[0],[0]]
0
1
2
3
start
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
0
1
2
3
start
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
dist=1
0
1
2
3
end
next
DP: mask 0001
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
0001
0
∞
∞
∞
0010
∞
0
∞
∞
0011
∞
1
∞
∞
0100
∞
∞
0
∞
1000
∞
∞
∞
0
dp[0101][2] =
0
+
1
=
1
dist=1
0
1
2
3
end
next
DP: mask 0011
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
0001
0
∞
∞
∞
0010
∞
0
∞
∞
0011
1
1
∞
∞
0100
∞
∞
0
∞
0101
∞
∞
1
∞
0110
∞
∞
2
∞
0111
∞
∞
2
∞
1000
∞
∞
∞
0
1001
∞
∞
∞
1
1010
∞
∞
∞
2
dp[0111][2] =
1
+
1
=
2
improved
0
1
2
3
DP: mask 0101
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
0001
0
∞
∞
∞
0010
∞
0
∞
∞
0011
1
1
∞
∞
0100
∞
∞
0
∞
0101
1
∞
1
∞
0110
∞
2
2
∞
0111
∞
∞
2
∞
1000
∞
∞
∞
0
1001
∞
∞
∞
1
1010
∞
∞
∞
2
1011
∞
∞
∞
2
1100
∞
∞
∞
2
visited set
0101
— extend each end node to an unvisited node
dist=1
0
1
2
3
end
next
DP: mask 0110
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
0
1
2
3
mask
0001
0
∞
∞
∞
0010
∞
0
∞
∞
0011
1
1
∞
∞
0100
∞
∞
0
∞
0101
1
∞
1
∞
0110
∞
2
2
∞
0111
3
2
2
∞
1000
∞
∞
∞
0
1001
∞
∞
∞
1
1010
∞
∞
∞
2
1011
∞
∞
∞
2
1100
∞
∞
∞
2
1101
∞
∞
∞
2
1110
∞
∞
∞
4
dp[0111][0] =
2
+
1
=
3
dist=1
0
1
2
3
end
next
DP: mask 1000
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
0
1
2
3
mask
0001
0
∞
∞
∞
0010
∞
0
∞
∞
0011
1
1
∞
∞
0100
∞
∞
0
∞
0101
1
∞
1
∞
0110
∞
2
2
∞
0111
3
2
2
∞
1000
∞
∞
∞
0
1001
1
∞
∞
1
1010
∞
∞
∞
2
1011
∞
∞
∞
2
1100
∞
∞
∞
2
1101
∞
∞
∞
2
1110
∞
∞
∞
4
1111
∞
∞
∞
4
dp[1001][0] =
0
+
1
=
1
improved
0
1
2
3
DP: mask 1010
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
0
1
2
3
mask
0001
0
∞
∞
∞
0010
∞
0
∞
∞
0011
1
1
∞
∞
0100
∞
∞
0
∞
0101
1
∞
1
∞
0110
∞
2
2
∞
0111
3
2
2
∞
1000
∞
∞
∞
0
1001
1
∞
∞
1
1010
∞
2
∞
2
1011
∞
2
∞
2
1100
∞
∞
2
2
1101
∞
∞
2
2
1110
∞
∞
∞
4
1111
∞
∞
∞
4
visited set
1010
— extend each end node to an unvisited node
dist=2
0
1
2
3
end
next
DP: mask 1011
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
0
1
2
3
mask
0001
0
∞
∞
∞
0010
∞
0
∞
∞
0011
1
1
∞
∞
0100
∞
∞
0
∞
0101
1
∞
1
∞
0110
∞
2
2
∞
0111
3
2
2
∞
1000
∞
∞
∞
0
1001
1
∞
∞
1
1010
∞
2
∞
2
1011
3
2
∞
2
1100
∞
∞
2
2
1101
∞
∞
2
2
1110
∞
∞
4
4
1111
∞
∞
4
4
dp[1111][2] =
2
+
2
=
4
dist=1
0
1
2
3
end
next
DP: mask 1101
answer = ?
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
0
1
2
3
mask
0001
0
∞
∞
∞
0010
∞
0
∞
∞
0011
1
1
∞
∞
0100
∞
∞
0
∞
0101
1
∞
1
∞
0110
∞
2
2
∞
0111
3
2
2
∞
1000
∞
∞
∞
0
1001
1
∞
∞
1
1010
∞
2
∞
2
1011
3
2
∞
2
1100
∞
∞
2
2
1101
3
∞
2
2
1110
∞
4
4
4
1111
∞
4
4
4
dp[1111][1] =
3
+
1
=
4
improved
0
1
2
3
answer
answer = 4
dp[mask][end] — min edges to visit `mask`, ending at `end`
0
1
2
3
mask
0
1
2
3
mask
0001
0
∞
∞
∞
0010
∞
0
∞
∞
0011
1
1
∞
∞
0100
∞
∞
0
∞
0101
1
∞
1
∞
0110
∞
2
2
∞
0111
3
2
2
∞
1000
∞
∞
∞
0
1001
1
∞
∞
1
1010
∞
2
∞
2
1011
3
2
∞
2
1100
∞
∞
2
2
1101
3
∞
2
2
1110
∞
4
4
4
1111
5
4
4
4
shortest path visiting all nodes = 4
algo
master
.
io
Step:
Start: Shortest Path Visiting All 4 Nodes using BFS + Bitmask DP
0 / 123
Input
Standard
Small
Triangle
Custom
graph
=
[[1,2,3],[0],[0],[0]]
0 / 123
algo
master
.
io
Step:
Start: Shortest Path Visiting All 4 Nodes using BFS + Bitmask DP
