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

Europe

Answers without the blur. Sign up and see all textbooks for free! 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. ### Want to see more solutions like these? 