Scribd
Upload
12 views2 pages

Dijkstra's Algorithm Worksheet Guide

Uploaded by

chikasaevans455
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
12 views2 pages

Dijkstra's Algorithm Worksheet Guide

Uploaded by

chikasaevans455
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Worksheet 5 Optimisation algorithms

Unit 8 Algorithms

Dijkstra’s Shortest Path Algorithm – Priority Queue

1. Use Dijkstra’s algorithm to find the shortest distance from A to every other node. Colour
each node as it is completed or visited (dequeued) and enter the temporary distances
on the graph, changing them if and when required to end up with the shortest
distances.

Show the state of the priority queue as each node is visited.

Priority queue

A=0 B=∞ C=∞ D=∞ E =∞ F=∞ G =∞ H =∞

C= 3 B=15 D=∞ E =∞ F=∞ G =∞ H =∞

D= 5 B = 15 E =∞ F=∞ G =∞ H =∞

G=6 F = 10 B= 15 E =∞ H =∞

F = 10 B = 15 E =∞ H =∞

B = 15 E = 15 H =∞

E = 15 H=∞

H = 27

1
Worksheet 5 Optimisation algorithms
Unit 8 Algorithms

13

3
6
J
10

Priority queue

A= B= C= D=∞ E= F= G= H= I= J= K=

You might also like