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