Is taking the minimum of multiple weighted edges between 2 nodes in graph optimal ?

Question

In weighted graphs, if shortest path is asked to be calculated .. and it's possible that any 2 nodes have multiple edges with different weights connecting them.

---

On applying Floyd-Warshall algorithm or Dijkstra's algorithm : If there are multiple edges between 2 nodes, Can we take the minimum weighted edge and neglect the others ?

If so, can anyone prove that ? Thanks in advance

Answer 1

Yes, you can take the minimum. Imagine you took not the minimum edge and found a route, now if you replace that edge with a shorter one, the new route will be shorter.

Answer 2

Well, it depends. Are all the weights representing the same criteria? Eg) Consider the problem of shortest path planning in autonomous vehicles. There may be more than one criteria to take care like

• Time taken to reach destination
• number of tolls between the intermediate points
• quality of the road or safety factor[history of accidents happened in that route]

So it depends on the problem statement.