Graph Algorithms: Dijkstra BFS DFS and A*

A-Level Computer Science · Algorithms

Graph Algorithms: Dijkstra, BFS, DFS, and A*

Graph algorithms are fundamental to computer science, powering everything from sat-nav routing to social network analysis. At A-Level, you need to understand how these algorithms work, trace them by hand, and compare their efficiency.

Graph Terminology Recap

Term	Meaning
Vertex (node)	A point in the graph
Edge (arc)	A connection between two vertices
Weighted graph	Edges have numerical costs/distances
Directed graph (digraph)	Edges have a direction
Adjacency list	Each vertex stores a list of its neighbours
Adjacency matrix	2D array where entry [i][j] = weight of edge from i to j

Breadth-First Search (BFS)

BFS explores all neighbours at the current depth before moving deeper. It uses a queue (FIFO).

Algorithm:

1. Enqueue the start node and mark it as visited

2. While the queue is not empty:

Dequeue the front node
For each unvisited neighbour: mark as visited, record the parent, enqueue it

3. Stop when the target is found (or queue is empty)

Properties:

Finds the shortest path in an unweighted graph (fewest edges)
Time complexity: O(V + E) where V = vertices, E = edges
Space complexity: O(V) for the queue and visited set
Explores level by level — like ripples spreading out from a stone dropped in water

Trace example for a graph A—B—D, A—C—D, B—C:

Starting from A, queue: [A] → visit A, enqueue B, C → [B, C] → visit B, enqueue D → [C, D] → visit C (D already queued) → [D] → visit D. Path A→B→D (2 edges) or A→C→D (2 edges).

Depth-First Search (DFS)

DFS explores as deep as possible before backtracking. It uses a stack (LIFO) — or recursion (which uses the call stack).

Algorithm:

1. Push the start node onto the stack

2. While the stack is not empty:

Pop the top node
If not visited: mark as visited, push all unvisited neighbours

3. Stop when the target is found (or stack is empty)

Recursive version:

DFS(node):
    mark node as visited
    for each unvisited neighbour of node:
        DFS(neighbour)

Properties:

Does not guarantee the shortest path
Time complexity: O(V + E)
Space complexity: O(V) (depth of recursion can be up to V)
Useful for: detecting cycles, topological sorting, maze generation, checking connectivity

Dijkstra's Algorithm

Dijkstra's finds the shortest path in a weighted graph with non-negative weights.

Algorithm:

1. Set distance to start = 0, all others = ∞. All nodes unvisited.

2. Set current node = start

3. For each unvisited neighbour of current:

Calculate tentative distance = distance[current] + edge weight
If tentative < distance[neighbour]: update distance[neighbour] and record parent

4. Mark current as visited

5. Set current = unvisited node with smallest distance

6. Repeat from step 3 until target is visited (or all reachable nodes visited)

Trace table format:

Node	A	B	C	D	E	Visited
Init	0	∞	∞	∞	∞	{}
Visit A	0	4	2	∞	∞	{A}
Visit C	0	3	2	8	∞	{A,C}
Visit B	0	3	2	5	10	{A,C,B}
...

Properties:

Always finds the optimal path (with non-negative weights)
Time complexity: O(V²) with a simple array, O((V+E) log V) with a priority queue (min-heap)
Does not work with negative edge weights — use Bellman-Ford instead
Greedy algorithm — always picks the nearest unvisited node

A* Algorithm

A* is an informed (heuristic) search that improves on Dijkstra by using an estimate of the remaining distance. It is widely used in game AI and navigation.

Key formula:

f(n) = g(n) + h(n)

where:

g(n) = actual cost from start to node n (like Dijkstra)
h(n) = heuristic estimate of cost from n to the goal
f(n) = estimated total cost through n

Algorithm: Same as Dijkstra, but select the unvisited node with the smallest f(n) (not just g(n)).

Heuristic requirements:

Must be admissible: h(n) ≤ actual cost (never overestimates)
Common heuristics: straight-line distance (Euclidean), Manhattan distance (grid-based)
If h(n) = 0 for all n, A* reduces to Dijkstra
If h(n) is perfect, A* goes straight to the goal

*Why A is faster:** The heuristic guides the search toward the goal, avoiding exploring irrelevant areas of the graph. Dijkstra explores in all directions equally.

Comparison Table

Feature	BFS	DFS	Dijkstra	A*
Data structure	Queue	Stack	Priority queue	Priority queue
Weighted graphs?	No (unweighted only)	No	Yes	Yes
Optimal?	Yes (unweighted)	No	Yes	Yes (if h admissible)
Complete?	Yes	Yes (finite graphs)	Yes	Yes
Time complexity	O(V+E)	O(V+E)	O(V²) or O((V+E)log V)	Depends on heuristic
Uses heuristic?	No	No	No	Yes

Implementation Considerations

Adjacency list vs adjacency matrix:

	Adjacency list	Adjacency matrix
Space	O(V + E)	O(V²)
Check if edge exists	O(degree)	O(1)
Find all neighbours	O(degree)	O(V)
Best for	Sparse graphs	Dense graphs

Most real-world graphs are sparse (E << V²), so adjacency lists are usually preferred.

Applications

Algorithm	Real-world use
BFS	Social network "degrees of separation", web crawlers, shortest route in unweighted networks
DFS	Maze solving, detecting cycles, topological sort (build dependencies), garbage collection
Dijkstra	GPS navigation (road networks), network routing (OSPF protocol)
A*	Game pathfinding (enemy AI), robotics navigation, puzzle solving (15-puzzle)

Exam Tips

Be ready to trace any of these algorithms step-by-step on a given graph — show your working in a clear table
For Dijkstra, always show the distance table updating at each step
Know that BFS finds shortest paths in unweighted graphs; Dijkstra is needed for weighted graphs
A* questions will give you the heuristic values — you just need to compute f = g + h and pick the minimum
Common exam error: forgetting that DFS does not find shortest paths
If asked to compare algorithms, discuss time complexity, optimality, and space usage

Graph Algorithms: Dijkstra BFS DFS and A*