Download: Dijkstra Shortest Path
The Graph Data Structure:
A graph is a data type, which is made nodes. These nodes are known as ‘vertices’. These vertices are joined by connections called edges. Unlike a tree data structure, a graph does not have a predictable/regular structure.
Weighted Graph:
- The edges have numerical ‘weights’
- The weight represents cost, distance or effort.
- For example, the distance on a map.
Directed Graph:
Dijkstra’s Algorithm:
This is a way of computing the shortest path between two nodes on a graph.
- Look for the shortest path from the start node.
- Then the shortest path from that node and so on.
- Work through all possible routes, shortest first.
- Eventually one of the routes will reach the target node.
- We will be using this graph as an example.
- Let’s find the quickest route from A to B
- Let’s first draw a table for our working out
| Name: | Linked From: | Distance: | Status |
| A | – | 0 | Active |
| B | |||
| C | |||
| D |
- A is the ‘active node’ and the node we are starting from.
| Name: | Linked From: | Distance: | Status |
| A | – | 0 | Done |
| B | A | 6 | |
| C | A | 3 | |
| D |
- We then fill in the distances of the nodes that are connected to A.
- Node A is no longer being used, so we label it as ‘done’ because we will not be visiting it again.
| Name: | Linked From: | Distance: | Status |
| A | – | 0 | Done |
| B | A | 6 | |
| C | A | 3 | Active |
| D |
- We will now pick the next node. We pick the node with the smallest value, which is C.
- C is now active.
- We now have to find out which nodes we can get from C
| Name: | Linked From: | Distance: | Status |
| A | – | 0 | Done |
| B | A | 6 | |
| C | A | 3 | Active |
| D | C | 4 |
- You can get to D from node C.
- The total distance to D from A is 4. (3 + 1 = 4)
- We can get to B from C. However, the total distance from A, to C to B is 7 (3+4=7). This is longer than going from A straight to B, which is 6. We don’t use this route as it is longer.
| Name: | Linked From: | Distance: | Status |
| A | – | 0 | Done |
| B | A | 6 | |
| C | A | 3 | Done |
| D | C | 4 | Active |
- We are now done with node C, so we make the status as done.
- Node D has the next smallest value, so we choose that as our active node.
| Name: | Linked From: | Distance: | Status |
| A | – | 0 | Done |
| B | A | 6 | Can Replace |
| C | A | 3 | Done |
| D | C | 4 | Active |
- The distance from D to B is 1. The distance from A to C to D is 4. 4+1 is 5.
- The distance from A to C to D to B is 5. This is shorter than A to B.
- We can now replace A to B with A – C – D – B
| Name: | Linked From: | Distance: | Status |
| A | – | 0 | Done |
| B | D | 5 | |
| C | A | 3 | Done |
| D | C | 4 | Done |
- The shortest path to B is the route: A-C-D-B, with the distance 5
In summary:
- The node with the smallest value becomes the active node
- Find all nodes you can get to from the active node.
- Calculate the total distance and only replace if the value is smaller.
- The node is then done and not used again.
- Repeat there are no more possible routes to the target node.
