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)

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)

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)

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)

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)

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)

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²)

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)

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²)

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.