Shortest path with maximum minimum edge weight

A question is this type if and only if it asks to find a route where the minimum weight among all edges on the route is as large as possible (minimax problem).

1 questions · Challenging +1.2

Sort by: Default | Easiest first | Hardest first
OCR MEI D1 2007 June Q5
16 marks Challenging +1.2
5 The table shows the weights on the arcs of a network.
ABCDEFG
A-11--1035
B11-85--14
C-8-2-7-
D-52-6--
E10--6-6-
F3-7-6--
G514-----
  1. Draw the network.
  2. Apply Dijkstra's algorithm to find the least weight route from G to D. (Do this on the network you drew for part (i).) Give your route and its total weight.
  3. Find by inspection the route from \(G\) to \(D\) such that the minimum of the weights for arcs on the route is as large as possible. Give your route and its minimum arc weight. Give an application in which this might be needed.
  4. Consider how Dijkstra's algorithm could be modified to solve the problem in part (iii). Explain how to update working values. Explain how to select the next vertex to be permanently labelled.