Course contentsShow
← Computer Science
Lesson 977 of 2,87223. Shortest Path AlgorithmsFree lesson

Early Termination for Single Target Queries

Optimizing Dijkstra's to stop once the target vertex is processed instead of computing all paths.

Early Termination for Single Target Queries

What you'll learn: How to make Dijkstra's algorithm stop early when you only need the shortest path to one specific destination.

The Core Idea

By default, Dijkstra's algorithm computes shortest paths from a source vertex to all other vertices in the graph. But often you just want the shortest path to a single target vertex—say, from your home to the airport, not from your home to every location in the city.

The optimization is simple: stop the algorithm as soon as you process (extract from the priority queue) the target vertex. At that moment, you've found the shortest path to your destination, and there's no need to continue exploring other vertices.

Why This Works

Dijkstra's algorithm processes vertices in order of increasing distance from the source. Once a vertex is extracted from the priority queue, its shortest distance is finalized and will never improve. So when your target vertex comes out of the queue, you know:

  1. You've found the shortest path to it
  2. Any remaining vertices in the queue are either farther away or irrelevant to your target

Think of it like searching for a specific item in a store: once you find it, you don't need to browse every other aisle.

Implementation Note

In the main loop where you extract vertices from the priority queue, add a check:

if current_vertex == target:
    break  # Done! Early termination

This can dramatically speed up queries in large graphs, especially when the target is relatively close to the source.

Key Takeaway: When you only need the shortest path to a single target vertex, terminate Dijkstra's algorithm immediately after processing that target, avoiding unnecessary work on the rest of the graph.