• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q18E

Expert-verified
Found in: Page 717

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

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

The shortest path between two vertices need not be unique.

See the step by step solution

## Step 1: Given data

The graph is given as,

## Step 2: Concept used of Dijkstra’s algorithm

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

## Step 3: 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.