Shortest Path Algorithm Tutorial with Problems

In this tutorial, we’ll explore the most widely used shortest path algorithms that are essential in the study of Data Structures and Algorithms. Each algorithm offers unique advantages and limitations depending on the specific requirements of the problem. We’ll also break down their time and space complexities, which are commonly discussed in technical interviews. If you’re eager to start learning these concepts right away, consider signing up for free courses and receive the latest course updates to boost your skills effectively.

What Are the Shortest Path Algorithms?

Shortest path algorithms are designed to determine the minimum travel cost or distance from a source node to a destination node in a graph, while optimizing both time and space complexity.

Types of Shortest Path Algorithms

Given that graphs can vary—such as weighted, unweighted, cyclic, or even containing negative weights—no single algorithm can efficiently solve all types. To manage different scenarios effectively, shortest path algorithms are classified into two main categories:

Single Source Shortest Path Algorithms

In this algorithm type, we determine the shortest path from a single source node to all other nodes in the graph.

Algorithms include:

• Depth-First Search (DFS)
• Breadth-First Search (BFS)
• Multi-Source BFS
• Dijkstra’s Algorithm
• Bellman-Ford Algorithm
• Topological Sort
• A* Search Algorithm
  
  

All Pair Shortest Path Algorithms

Contrary to single-source shortest path algorithms, here we determine the shortest path between every possible pair of nodes.

Algorithms include:

• Floyd-Warshall Algorithm
• Johnson’s Algorithm
  
  

Let’s discuss these algorithms one by one.

1. Shortest Path Algorithm using Depth-First Search (DFS)

DFS recursively explores adjacent nodes until no more valid recursive calls are possible.

Note: DFS can only be used for shortest path calculation in acyclic graphs (trees). For cyclic graphs, DFS can’t guarantee the shortest path due to multiple possible paths. If there’s no path between source and destination, return -1 as the shortest path.

Algorithm:

• Distance of source to itself is 0.
• Start DFS from the source.
• Update neighbor’s distance = edge weight + parent node’s distance.
• End when all leaf nodes are visited. 

Complexity:

• Time: O(N)
• Space: O(N) (due to recursive stack)

Real World Application:

Finding the path between nodes in a hierarchical file‐system (tree) where every folder and subfolder is treated as a node and edges are unweighted—e.g., locating a specific file’s directory path in an operating system’s folder structure.

2. Breadth-First Search (BFS) for Shortest Path Algorithm

BFS works well for unweighted graphs and ensures the shortest path in terms of number of edges. Why it works: BFS explores all nodes at distance d before moving to d+1.

Algorithm:

• Use a queue with {node, distance} pairs.
• Start with {source, 0}.
• While queue is not empty:
  
  
  • Pop the front node.
  • Record its distance.
  • Push all unvisited neighbors with distance + 1.
    
    

Complexity:

• Time: O(V + E)
• Space: O(V)

Real World Application:

Finding the minimum number of transfers in an unweighted public‐transit network (e.g., subway lines) where each station is a node and each direct ride between stations is an edge—BFS yields the fewest transfers from one station to another.

3. Multi-Source BFS for Shortest Path Algorithm

Multi-Source BFS starts simultaneously from multiple source nodes.

Algorithm:

• Push all source nodes into queue with distance 0.
  
  
• While queue is not empty:
  
  
  • Pop front node.
  • Record its distance.
  • Push unvisited neighbors with distance + 1.
    
    

Complexity:

• Time: O(V + E)
• Space: O(V)

Real World Application:

Modeling the spread of emergency alerts from multiple dispatch centers in a city—each dispatch center is a source, and you want to know how quickly (in number of road‐hops) the alert reaches each neighborhood.

4. Dijkstra’s Algorithm for Shortest Path Algorithm

Dijkstra’s algorithm is used for weighted graphs with non-negative weights using a greedy approach.

Algorithm:

• Initialize distances to all nodes as ∞; source = 0.
• Use a min-heap or priority queue.
• Pick node with the smallest distance.
• Update distances for its neighbors if a shorter path is found.
  
  

Complexity:

• Time: O(E * log V)
• Space: O(V)

Real World Application:

GPS navigation systems compute the quickest driving route on a road network where nodes are intersections and edges are road segments weighted by travel time—Dijkstra’s finds the minimum‐travel‐time path from your current location to the destination.

If you want to master this algorithm and many more, check out the DSA course to deepen your understanding.

5. Bellman-Ford Algorithm for Shortest Path Algorithm

Unlike Dijkstra, Bellman-Ford handles negative weights and detects negative cycles.

Algorithm:

• Initialize dist[] with ∞, source = 0.
• Relax all edges V – 1 times:
  dist[v] = min(dist[v], dist[u] + weight)
  
  

Complexity:

• Time: O(V * E)
• Space: O(V)

Real World Application:
Currency‐exchange arbitrage detection, where each currency pair’s exchange rate can be represented as an edge with weight = –log(rate). Bellman-Ford detects if there’s a cycle whose total weight < 0, indicating a guaranteed profit loop.

6. Topological Sort for Shortest Path in DAGs

Used for shortest paths in Directed Acyclic Graphs (DAGs).

Working:

• Nodes with in-degree 0 are source nodes.
• Use topological sort followed by edge relaxation.
  
  

Complexity:

• Time: O(V + E)
• Space: O(V)

Real World Application:

Project scheduling with task dependencies (e.g., building software features where some modules must be completed before others). Each task is a node, directed edges represent “must finish before,” and weights represent time; topological sort plus relaxation finds the minimum completion time for every task.

7. Floyd-Warshall Algorithm for Shortest Path

Solves all-pairs shortest path problem using Dynamic Programming.

Algorithm:

• Initialize dist[][] matrix from input graph.
• For each vertex k, update every dist[i][j]:
  dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
  
  

Complexity:

• Time: O(V³)
• Space: O(V²)

Real World Application:

Computing the shortest travel times between all pairs of major train stations in a national rail network, where the result is used to quickly answer queries like “What’s the fastest route from Station A to Station B via any number of transfers?”

8. A* Search Algorithm for Shortest Path

A* is a heuristic-based algorithm used in games and map services. Key: It combines cost to reach a node + estimated cost to goal.

Complexity:

• Time: O(E * log V)
• Space: O(V)

Real World Application:

Pathfinding for non‐player characters in video games (e.g., a character navigating a 3D environment), where the heuristic is typically Euclidean or Manhattan distance to the goal—A* finds near‐optimal routes very efficiently.

9. Johnson’s Algorithm for Shortest Path

Used for all-pairs shortest paths, including graphs with negative edge weights.

Steps:

• Re-weight all edges to make them non-negative using Bellman-Ford.
• Apply Dijkstra from each vertex.
  
  

Complexity:

• Time: O(V² * log V + V * E)
• Space: O(V²)

Real World Application:

Finding all‐pairs shortest routes in a continental airline network where some legs may have negative‐adjusted costs due to rebates or codeshares—Johnson’s scales better than Floyd-Warshall on sparse graphs.

Complexity Comparison of Shortest Path Algorithms

Real World Applications of Shortest Path Algorithms

1. GPS Navigation

Shortest path algorithms like Dijkstra or A* help GPS systems find the quickest or most efficient route from your location to a destination, considering traffic and road conditions.

2. Network Routing

In computer networks, routers use shortest path algorithms (e.g., OSPF with Dijkstra) to determine the most efficient path for data packets to travel across the internet.

3. Transportation Planning

City planners and logistics companies use these algorithms to optimize traffic flow, reduce travel time, and plan public transportation routes efficiently.

4. Airline Flight Planning

Airlines use shortest path algorithms to determine the most efficient flight paths between cities, minimizing fuel costs and travel time while considering air traffic and regulations.

5. Social Network Analysis

In platforms like Facebook or LinkedIn, shortest path algorithms are used to find degrees of separation between users or suggest connections through mutual friends.

6. Circuit Design

In VLSI and PCB design, shortest path algorithms help in laying out the shortest connections between components to minimize delay and material usage.

Frequently Asked Questions (FAQs)