Pathfinding and Shortest Paths
Algorithms like Dijkstra and A* find routes.
About this topic
Pathfinding algorithms find a route between two points in a graph or map, often the shortest or cheapest one. Breadth-first search finds the path with fewest steps in an unweighted graph by exploring outward level by level. Dijkstra's algorithm handles weighted edges, such as distances or travel times, by always expanding the closest unvisited node and updating the best known distances to its neighbours.
The A star algorithm improves on this by adding a heuristic, an estimate of the remaining distance to the goal, so it explores promising directions first. For example, going from A to D with routes A to B to D costing 7 and A to C to D costing 5, Dijkstra correctly picks the second. It relies on edge weights not being negative.
These ideas drive GPS navigation, delivery routing, network packet routing and the movement of characters in video games. A common misconception is that the path with the fewest turns or nodes is always shortest in distance; weights change the answer. Another is thinking a greedy choice at each junction always gives the best total. Sketch a small graph and track distances in a table to understand the algorithm.
Key ideas
- Graphs model maps
- Weights are distances
- GPS uses them
Quick check
Use cases: where Pathfinding and Shortest Paths helps
- Homework: review the key idea behind Pathfinding and Shortest Paths before you start a problem set.
- Exam revision: use the quick check to test whether you can recall Pathfinding and Shortest Paths without notes.
- Visual learning: play with the interactive lab to see how Pathfinding and Shortest Paths changes when you adjust its inputs.
- Teaching a friend: explain Pathfinding and Shortest Paths in your own words, then compare your version with the key ideas.
Computing ideas run phones, search engines, games and the wider internet.
Frequently asked questions
What is Pathfinding and Shortest Paths?
Algorithms like Dijkstra and A* find routes.
What will I learn in Pathfinding and Shortest Paths?
Graphs model maps. Weights are distances. GPS uses them.
Is Pathfinding and Shortest Paths part of Computer Science?
Yes. It is one of 80 Computer Science topics on LearnViz HighSchoolEdu, with 3 key ideas, a live animation and a quick check.
Does the Pathfinding and Shortest Paths lab work on a phone or tablet?
Yes. The animation resizes to fit your screen and supports touch, so you can drag, tap and slide with your finger.
How should I study Pathfinding and Shortest Paths?
Read the summary and key ideas first, play with the interactive lab to see the idea in motion, then answer the quick check. If you get a question wrong, go back to the key idea it tests.
Do I need an account, and is my progress saved?
No account is needed. Marking a topic as learned is saved in your own browser, so it stays on that device and is not sent to a server.