Search topics

Search
1 of 8 0-day streak

Dijkstra's algorithm for shortest distances and routes

DIFFICULTYintrostandardchallengeexam
QUESTION TYPEMix of allChange
nextStep; core; five vertex sparsenextStep; core; five vertex meshNOWMix of allRecommended
Question 1 of 8

Calculator allowed

Consider this weighted network of power lines between service sites. Each edge label gives the installation cost in dollars. Apply Dijkstra's algorithm from Substation

Weighted network. Vertices in listed order: [Depot | Pump | Battery | Substation | Factory]. Full edge list: Factory–Substation ($465); Substation–Pump ($833); Depot–Pump ($703); Battery–Depot ($641); Pump–Factory ($483); Battery–Factory ($365); Depot–Factory ($195); Depot–Substation ($389).$465$833$703$641$483$365$195$389DepotPumpBatterySubstationFactory
(a)2 marks

The table shows the state immediately before Depot becomes permanent

Labels before relaxing from Depot
VertexStatusDistance labelPredecessor
Depottemporary389Substation
Pumptemporary833Substation
Batterytemporarynot yet labelled-
Substationpermanent0-
Factorytemporary465Substation

Complete the distance labels after Depot becomes permanent and its eligible edges are relaxed

Labels after relaxing from Depot
VertexStatusDistance labelPredecessor
Depotpermanent389Substation
Pumptemporary?Substation
Batterytemporary?Depot
Substationpermanent0-
Factorytemporary465Substation
(b)1 mark

Which vertex should receive the next permanent label?