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 roads between coastal towns. Each edge label gives the road distance in kilometres. Apply Dijkstra's algorithm from Portland

Weighted network. Vertices in listed order: [Warrnambool | Port Fairy | Portland | Anglesea | Apollo Bay]. Full edge list: Port Fairy–Portland (23 km); Warrnambool–Port Fairy (11 km); Warrnambool–Anglesea (9 km); Apollo Bay–Port Fairy (43 km); Anglesea–Portland (31 km); Port Fairy–Anglesea (21 km); Warrnambool–Apollo Bay (53 km).23 km11 km9 km43 km31 km21 km53 kmWarrnamboolPort FairyPortlandAngleseaApollo Bay
(a)2 marks

The table shows the state immediately before Port Fairy becomes permanent

Labels before relaxing from Port Fairy
VertexStatusDistance labelPredecessor
Warrnambooltemporarynot yet labelled-
Port Fairytemporary23Portland
Portlandpermanent0-
Angleseatemporary31Portland
Apollo Baytemporarynot yet labelled-

Relax the eligible edges from Port Fairy, then enter the retained temporary labels

Labels after relaxing from Port Fairy
VertexStatusDistance labelPredecessor
Warrnambooltemporary?Port Fairy
Port Fairypermanent23Portland
Portlandpermanent0-
Angleseatemporary?Portland
Apollo Baytemporary66Port Fairy
(b)1 mark

Select the next vertex to make permanent