Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Minimum Weighted Subgraph With Required Paths
Bookmark
Brute Force
Three Dijkstra
Input
6 Nodes
4 Nodes
5 Nodes
Custom
n
=
6
,
edges
=
[[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]]
,
src1
=
0
,
src2
=
1
,
dest
=
5
2
6
3
5
1
4
2
1
0
1
2
3
4
5
s1
s2
d
0
1
2
3
4
5
dist1:
∞
∞
∞
∞
∞
∞
dist2:
∞
∞
∞
∞
∞
∞
distM:
∞
∞
∞
∞
∞
∞
src1
src2
dest
Default
Current
Visited
Checking
2
6
3
5
1
4
2
1
0
1
2
3
4
5
s1
s2
d
0
1
2
3
4
5
dist1:
∞
∞
∞
∞
∞
∞
dist2:
∞
∞
∞
∞
∞
∞
distM:
∞
∞
∞
∞
∞
∞
src1
src2
dest
Default
Current
Visited
Checking
Dijkstra from src1 (0)
2
6
3
5
1
4
2
1
0
1
2
3
4
5
s1
s2
d
0
1
2
3
4
5
dist1:
0
3
2
5
8
6
dist2:
∞
∞
∞
∞
∞
∞
distM:
∞
∞
∞
∞
∞
∞
src1
src2
dest
Default
Current
Visited
Checking
Dijkstra from src2 (1)
2
6
3
5
1
4
2
1
0
1
2
3
4
5
s1
s2
d
0
1
2
3
4
5
dist1:
0
3
2
5
7
6
dist2:
3
0
5
∞
5
9
distM:
∞
∞
∞
∞
∞
∞
src1
src2
dest
Default
Current
Visited
Checking
Dijkstra from meeting node 0
2
6
3
5
1
4
2
1
0
1
2
3
4
5
s1
s2
d
0
1
2
3
4
5
dist1:
0
3
2
5
7
6
dist2:
3
0
5
8
5
6
distM:
0
∞
2
∞
∞
∞
m=0: 0 + 3 + ?
src1
src2
dest
Default
Current
Visited
Checking
Dijkstra from meeting node 0
2
6
3
5
1
4
2
1
0
1
2
3
4
5
s1
s2
d
0
1
2
3
4
5
dist1:
0
3
2
5
7
6
dist2:
3
0
5
8
5
6
distM:
0
3
2
5
7
6
m=0: 0 + 3 + ?
src1
src2
dest
Default
Current
Visited
Checking
Dijkstra from meeting node 1
Answer: 9
2
6
3
5
1
4
2
1
0
1
2
3
4
5
s1
s2
d
0
1
2
3
4
5
dist1:
0
3
2
5
7
6
dist2:
3
0
5
8
5
6
distM:
3
0
5
∞
5
9
m=1: 3 + 0 + ?
src1
src2
dest
Default
Current
Visited
Checking
Dijkstra from meeting node 2
Answer: 9
2
6
3
5
1
4
2
1
0
1
2
3
4
5
s1
s2
d
0
1
2
3
4
5
dist1:
0
3
2
5
7
6
dist2:
3
0
5
8
5
6
distM:
∞
1
0
∞
∞
∞
m=2: 2 + 5 + ?
src1
src2
dest
Default
Current
Visited
Checking
Dijkstra from meeting node 2
Answer: 9
2
6
3
5
1
4
2
1
0
1
2
3
4
5
s1
s2
d
0
1
2
3
4
5
dist1:
0
3
2
5
7
6
dist2:
3
0
5
8
5
6
distM:
4
1
0
3
5
6
m=2: 2 + 5 + ?
src1
src2
dest
Default
Current
Visited
Checking
Dijkstra from meeting node 3
Answer: 9
2
6
3
5
1
4
2
1
0
1
2
3
4
5
s1
s2
d
0
1
2
3
4
5
dist1:
0
3
2
5
7
6
dist2:
3
0
5
8
5
6
distM:
∞
∞
∞
0
2
3
m=3: 5 + 8 + 3 = 16
src1
src2
dest
Default
Current
Visited
Checking
Phase 4: Find Meeting Node
Answer: 9
2
6
3
5
1
4
2
1
0
1
2
3
4
5
s1
s2
d
0
1
2
3
4
5
dist1:
0
3
2
5
7
6
dist2:
3
0
5
8
5
6
distM:
∞
∞
∞
∞
∞
0
src1
src2
dest
Default
Current
Visited
Checking
algo
master
.
io
Step:
6 nodes and 9 edges. Both sources must reach 5 over one shared subgraph.
0 / 168
Input
6 Nodes
4 Nodes
5 Nodes
Custom
n
=
6
,
edges
=
[[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]]
,
src1
=
0
,
src2
=
1
,
dest
=
5
0 / 168
algo
master
.
io
Step:
6 nodes and 9 edges. Both sources must reach 5 over one shared subgraph.
