OCR A Level CS 2.3.5 Path Finding Algorithms

What is the purpose of path-finding algorithms?

To determine the shortest or most efficient route between two points in a graph.

Where are path-finding algorithms used?

✅ Navigation systems (Google Maps, GPS)
✅ Computer networks (routing data packets efficiently)
✅ AI in games (NPC movement, shortest paths)

What is Dijkstra’s algorithm used for?

Finding the shortest path between nodes in a weighted graph.

How does Dijkstra’s algorithm work?

1⃣ Assign infinite distance to all nodes except the start node (distance = 0).
2⃣ Add the start node to a priority queue.
3⃣ Select the node with the smallest distance, update its neighbours if a shorter path is found.
4⃣ Repeat until the shortest path to the target node is found.

Why is Dijkstra’s algorithm efficient?

It guarantees the shortest path and avoids unnecessary calculations

What data structure is commonly used in Dijkstra’s algorithm?

A priority queue (ensures nodes with the shortest distances are processed first).

What is a real-world application of Dijkstra’s algorithm?

Network routing protocols (e.g., finding the fastest path for internet traffic).

What is the A* algorithm?

A path-finding algorithm that improves Dijkstra’s method by using heuristics.

What is a heuristic in A*?

A function that estimates the remaining distance to the goal, helping prioritize nodes.

How does A* differ from Dijkstra’s algorithm?

A* adds a heuristic cost to improve efficiency, meaning it finds the shortest path faster.

What is the formula used in A*?

Total Cost = Actual Cost (g) + Heuristic Cost (h)

• g = cost from start to current node

• h = estimated cost from current node to goal

When is A* more efficient than Dijkstra’s algorithm?

When good heuristics are available (e.g., in grid-based maps).

What is a drawback of A*?

❌ The effectiveness depends on the accuracy of the heuristic function.

Comparing Dijkstra’s and A*

Feature	Dijkstra’s Algorithm	A Algorithm*
Approach	Expands nodes based on shortest known distance	Uses a heuristic to guide search
Efficiency	Can explore unnecessary paths	Focuses on the most promising paths
Best for...	Networks, graphs with no heuristics	Grids, maps, AI navigation
Guarantees shortest path?	✅ Yes	✅ Yes (if heuristics are good)