Hi guys! I was working with this problem here.. I figured that I should add the weights on corresponding edges and then apply Dijkstra’s algorithm. Will this approach work? How should I prove it’s correctness ? I would love to hear your approaches for this problem…
No, this approach will not work because it will not always give the same result as the original weight metric. Consider a simple counter-example as shown below. The outer values are weight1 and inner ones are weight2.
(2)
// \\\\
// \\\\
8//1 1\\\\8
// \\\\
(0) (1)
\\\\ //
4\\\\4 4//4
\\\\ //
\\\\ //
(3)
By this approach,
cost(0-2-1) = (weight1(0-2)+weight2(0-2)) + (weight1(2-1)+weight2(2-1))
= (8+1) + (8+1) = 18
cost(0-3-1) = (weight1(0-3)+weight2(0-3)) + (weight1(3-1)+weight2(3-1))
= (4+4) + (4+4) = 16
However by the method described in the question,
cost(0-2-1) = (weight1(0-2)+weight1(2-1)) * (weight2(0-2)+weight2(2-1)) = (8+8) * (1+1) = 32 cost(0-3-1) = (weight1(0-3)+weight1(3-1)) * (weight2(0-3)+weight2(3-1)) = (4+4) * (4+4) = 64
You can still use Dijkstra’s algorithm using the weight1×weight2 metric, however because n will be between 2 and 20, a simple dfs/bfs is the way to go in my opinion 
1 Like