Question

Is a shortest path between two vertices in a weighted graph unique if the weights of edges are distinct?

Short answer

The shortest path between two vertices need not be unique.

Step-by-step solution

Given data

The graph is given as,

Concept used of Dijkstra’s algorithm 

Dijkstra's algorithm allows us to find the shortest path between any two vertices of a graph.

Find the least path

Consider the graph shown below with vertices

\(A,B\) and \(C\) with weight \(AB = 1\), weight \({\rm{AC}} = 2\) and weight \(BC = 3\)

In this case the weights are distinct but there are two shortest paths from \(B\) to \(C\): the direct path \(B,C\) and the path through \({\rm{A:B,A,C}}\) both having the same length 3 .

This example shows that the shortest path between vertices need not be unique (even) if the weights are distinct.