Dijkstra’s Algorithm Revision Notes for VCE SSCE General Mathematics

Dijkstra's Algorithm

What is Dijkstra's algorithm?

When working with small graphs, finding the shortest path from one vertex to another is relatively straightforward. However, when a graph has many vertices and edges, you need a systematic method (called an algorithm) to find the shortest path efficiently.

Dijkstra's algorithm (pronounced 'Dyke-stra') is a step-by-step process that helps you find the shortest path through a weighted graph. This algorithm was developed by Dutch computer scientist Edsger Wybe Dijkstra and has become fundamental to modern technology.

Real-world applications

Dijkstra's algorithm, and similar methods, are essential for:

GPS navigation systems
Computerised routing programmes
Scheduling systems
Network optimisation

infoNote

These applications need to quickly calculate the most efficient route from one location to another, just as Dijkstra's algorithm finds the shortest path through a graph. Every time you use a GPS or mapping application, you're benefiting from this algorithm!

The algorithm: step-by-step process

The algorithm follows five main steps, which you repeat until you reach your destination. Here's how it works:

Step 1: Mark your starting point

Assign your starting vertex a value of 0 (zero). Then circle both the vertex and this zero together. This circling makes the value permanent.

chatImportant

Important rule: Once you've circled a vertex and its value together, you cannot change it. This is the fundamental principle of Dijkstra's algorithm.

Step 2: Update connected vertices

Look at the vertex you most recently circled. Let's call this vertex $X$ and say it has a value of $d$ .

Now examine each vertex that connects directly to $X$ but hasn't been permanently circled yet. For each of these vertices (let's call one $Y$ ):

Calculate: $d +$ (weight of edge from $X$ to $Y$ )
If $Y$ doesn't have a temporary value yet, assign it this calculated value
If $Y$ already has a temporary value, compare the two values and keep whichever is smaller

infoNote

The key idea here is that you're exploring all possible paths and keeping track of the shortest distance found so far to each vertex.

Step 3: Make the smallest value permanent

Look at all the uncircled (temporary) values in your network. Find the smallest one and circle it to make it permanent.

Step 4: Repeat the process

Keep repeating Steps 2 and 3 until your destination vertex has a permanent (circled) value.

infoNote

You don't need to circle all vertices in the graph—only continue until the destination vertex is circled. This can save considerable time in large graphs!

Step 5: Backtrack to find the actual path

Once your destination has a permanent value, you know the length of the shortest path (it's the destination's value). To find the actual path itself, work backwards:

Start at the destination vertex
Move to the circled vertex where: vertex value = (destination value) − (edge weight)
Continue moving backwards, following this pattern, until you reach the starting vertex

Worked example: finding the shortest path

lightbulbExample

Worked Example: Finding the Shortest Path from A to F

Let's work through a complete example to see how Dijkstra's algorithm works in practice.

Question: Find the shortest path from vertex $A$ to vertex $F$ in the weighted graph below.

Solution

Step 1: Assign zero to the starting vertex

We start at vertex $A$ , so we assign it a value of $0$ and circle both the vertex and the zero together.

Vertex $A$ is our starting point
It gets a permanent value of $0$
The circle shows this value is permanent and cannot change

Step 2: Update vertices connected to A

The starting vertex $A$ connects directly to two vertices: $B$ and $C$ .

For vertex $B$ :

Edge weight from $A$ to $B$ = $2$
Value = $0 + 2 = 2$

For vertex $C$ :

Edge weight from $A$ to $C$ = $6$
Value = $0 + 6 = 6$

Now we circle the vertex with the lowest uncircled value. Since $2 \< 6$ , we circle vertex $B$ with its value of $2$ .

Step 3: Update vertices connected to B

Now vertex $B$ (with value $2$ ) is our most recently circled vertex. It connects to three vertices: $C$ , $D$ , and $E$ .

For vertex $E$ :

Edge weight from $B$ to $E$ = $2$
Value = $2 + 2 = 4$
This is a new value, so $E$ gets $4$

For vertex $D$ :

Edge weight from $B$ to $D$ = $3$
Value = $2 + 3 = 5$
This is a new value, so $D$ gets $5$

For vertex $C$ :

Edge weight from $B$ to $C$ = $2$
New calculated value = $2 + 2 = 4$
Existing value = $6$
Since $4 < 6$ , we update $C$ to $4$

Looking at all uncircled vertices, both $C$ and $E$ have the lowest value of $4$ . When there's a tie, it doesn't matter which you circle first. We'll circle $C$ .

Step 4: Continue the process

We repeat Step 3, working from newly circled vertices, until we reach $F$ .

The final result looks like this:

Vertex $F$ (our destination) has a permanent value of $7$ . This means the shortest path from A to F has a length of 7.

Step 5: Backtrack to find the route

Starting at $F$ (value $7$ ), we work backwards:

From $F$ $F$ ( $7$ $7$ ): Which connecting edge gives us $7 - \text{edge weight} = \text{circled vertex value}$ $7 - edge weight = circled vertex value$ ?
- Edge to $E$ has weight $3$ : $7 - 3 = 4$ ✓ (This equals $E$ 's value)
- Edge to $D$ has weight $5$ : $7 - 5 = 2$ ✗ (This doesn't equal $D$ 's value of $5$ )
- So we move to $E$
From $E$ $E$ ( $4$ $4$ ): $4 - 2 = 2$ $4 - 2 = 2$ ✓ (This equals $B$ $B$ 's value)
- So we move to $B$
From $B$ $B$ ( $2$ $2$ ): $2 - 2 = 0$ $2 - 2 = 0$ ✓ (This equals $A$ $A$ 's value)
- So we move to $A$

Answer: The shortest path from A to F is: A - B - E - F with a total length of 7.

Key rules to remember

chatImportant

Critical Rules for Dijkstra's Algorithm:

Permanence: Once you circle a vertex and its value, you cannot change it. The circle indicates the value is final.
Smallest wins: Always choose the smallest uncircled value when deciding which vertex to make permanent next.
No going backwards: Once a vertex has a value (even if not circled yet), you cannot assign it a larger value. You can only replace it with a smaller value.
Stop early: You don't need to label every vertex in the graph. Stop once your destination vertex is circled.
Two answers needed: Dijkstra's algorithm gives you both:
- The length of the shortest path (the final circled value at the destination)
- The route itself (found by backtracking)

Exam tips

infoNote

Exam Success Strategies:

Show your working clearly at each step. Draw the graph multiple times if needed to show progression.
When two vertices have the same temporary value, state that "it doesn't matter which is chosen" and circle one.
Always circle values to show they're permanent—this is crucial for the backtracking step.
Double-check your backtracking by adding up the edge weights along your route. The total should equal the destination vertex's final value.
If asked for the shortest path, give both the route (e.g., $A - B - E - F$ ) and the length (e.g., $7$ ).

Remember!

bookmarkSummary

Key Takeaways:

Dijkstra's algorithm is a systematic method for finding the shortest path through a weighted graph.
The algorithm works by progressively assigning and making permanent the shortest distances from the starting vertex to all other vertices.
Circle values to show they're permanent and cannot be changed.
Always choose the smallest uncircled value to make permanent next.
Find the actual shortest route by backtracking from the destination to the start.
The algorithm is widely used in real-world applications like GPS navigation and network routing.

Dijkstra’s Algorithm (VCE SSCE General Mathematics): Revision Notes