## Shortest Path

Question 1 |

Consider a weighted undirected graph with positive edge weights and let uv be an edge in the graph. It is known that the shortest path from the source vertex s to u has weight 53 and the shortest path from s to v has weight 65. Which one of the following statements is always true?

weight (u, v) < 12 | |

weight (u, v) ≤ 12 | |

weight (u, v) > 12 | |

weight (u, v) ≥ 12 |

Question 1 Explanation:

Weight (u, v) ≥ 12 (True)

If the weight (u, v) < 12 then

min. weight of (s, v) = weight of (s, u) + weight of (u, v)

= 53 + (<12)

= less than 65

If the weight (u, v) < 12 then

min. weight of (s, v) = weight of (s, u) + weight of (u, v)

= 53 + (<12)

= less than 65

There is 1 question to complete.