Shortest Path

Discover how to find the most efficient route between points in any network. Shortest path algorithms power GPS navigation, network routing, and logistics optimization. They turn complex routing problems into manageable computations that scale from simple maps to massive transportation networks.

The shortest path pattern finds the minimum cost path between nodes in a graph, where cost represents distance, time, money, or any other metric. A graph consists of vertices (nodes) connected by edges with weights representing the cost to travel between them.

Real-World Analogy

Think of the shortest path problem like planning a road trip. You want to get from your house to a destination using the least amount of time or fuel. Each road has a travel time or distance, and intersections are decision points. You could try every possible route, but that would take forever. Instead, you use smart strategies like always checking the quickest unvisited intersection (like Dijkstra) or exploring routes level by level (like BFS).

How It Works

The core idea is to systematically explore paths while tracking the minimum distance from the source to each node. Different algorithms use different strategies:

Dijkstra’s Algorithm - Greedy Exploration

Dijkstra always processes the closest unvisited node next, using a priority queue to efficiently select the minimum distance node.

  graph TD
    A[Start: source=0, others=∞] --> B[Initialize priority queue with source]
    B --> C{Queue empty?}
    C -->|No| D[Extract minimum distance node]
    D --> E{Node already visited?}
    E -->|Yes| C
    E -->|No| F[Mark node as visited]
    F --> G[For each neighbor: calculate new distance]
    G --> H{New distance smaller?}
    H -->|Yes| I[Update distance and add to queue]
    H -->|No| J[Skip this neighbor]
    I --> C
    J --> C
    C -->|Yes| K[Return distances array]

BFS for Unweighted Graphs - Level-by-Level

When all edges have the same weight (effectively 1), BFS explores nodes level by level, guaranteeing the first time we reach a node is via the shortest path.

  graph TD
    A[Start: source=0] --> B[Initialize queue with source]
    B --> C{Queue empty?}
    C -->|No| D[Dequeue next node]
    D --> E{Is this the target?}
    E -->|Yes| F[Return current distance]
    E -->|No| G[For each unvisited neighbor]
    G --> H[Set distance = current + 1]
    H --> I[Enqueue neighbor]
    I --> C
    C -->|Yes| J[No path found: return -1]

When to Use This Pattern

Use the shortest path pattern when:

• You need to find the minimum cost route between two or more nodes
• The problem involves weighted or unweighted graphs
• You need the minimum distance, time, or cost
• Network routing or pathfinding is involved
• The problem mentions “shortest,” “minimum,” “optimal,” or “least cost”
• You need to find if one node is reachable from another

Algorithm Selection Guide

Choose your algorithm based on:

• BFS: Unweighted graphs (all edges equal)
• Dijkstra: Non-negative weights, single source to all nodes
• Bellman-Ford: Negative weights present, need to detect negative cycles
• Floyd-Warshall: Dense graphs, need all-pairs shortest paths
• A*: Goal-directed search when a good heuristic exists

Complexity Analysis

Time Complexity

Where V is the number of vertices (nodes) and E is the number of edges.

Space Complexity

The space complexity comes from storing:

• Distance array for each node
• Priority queue or queue for frontier nodes
• Visited set to prevent revisiting
• Graph representation (adjacency list or matrix)

Common Mistakes

1. Using Dijkstra on negative weight graphs: Dijkstra cannot handle negative edge weights. Use Bellman-Ford instead.

2. Forgetting to mark visited nodes: This causes infinite loops in graphs with cycles. Always track visited nodes.

3. Incorrect graph representation: Using adjacency matrix for sparse graphs wastes space and time. Use adjacency lists instead.

4. Priority queue mismanagement: Not checking if dequeued nodes have stale distance values leads to incorrect results.

5. Not handling unreachable nodes: Always check if the target or all nodes were reached before returning.

6. Integer overflow: Summing edge weights can overflow. Use 64-bit integers or handle large values appropriately.

7. Wrong algorithm choice: Using O(V³) Floyd-Warshall when O((V + E) log V) Dijkstra would work much faster.

Next Steps

Now that you understand the concepts, explore the Code Templates to see how to implement these algorithms in different programming languages, then practice with real problems from LeetCode.