Dijkstra’s Shortest Path Algorithm is an algorithm used to find the shortest path between two nodes of a weighted graph.

Before investigating this algorithm make sure you are familiar with the terminology used when describing Graphs in Computer Science.

Let’s decompose the Dijkstra’s Shortest Path Algorithm step by step using the following example: (Use the tabs below to progress step by step).

**“Distance from A”**and set their

**“previous node”**to “A”.

**“visited”**and use the closest unvisited node to A as the

**current node**(e.g. in this case: Node C).

C -> B: 2 + 1 = 3 < 4 – Change Node B

C -> D: 2 + 8 = 10 < ∞ – Change Node D

C -> E: 2 + 10 = 12 < ∞ – Change Node E

We then repeat the same process always picking the closest unvisited node to A as the current node.

In this case node B becomes the current node.

Next “Current Node” will be D as it has the shortest distance from A amongst all unvisited nodes.

D -> Z 8+6 = 14 < ∞ – Change Node Z

We found a path from A to Z but it may not be the shortest one yet. So we need to carry on the process.

Next **“Current Node”**: E

**not**change node Z.

Read the path from Z to A using the previous node column:

Z > D > B > C > A

So the Shortest Path is:

**A – C – B – D – Z**with a length of**14**#### Your Task

Node | Status | Shortest Distance from A | Previous Node |

A | |||

B | |||

C | |||

D | |||

E | |||

F | |||

Z |

**Shortest Path?**

**Length?**

Node | Status | Shortest Distance from A | Previous Node |

A | |||

B | |||

C | |||

D | |||

E | |||

F | |||

Z |

**Shortest Path?**

**Length?**