DSA Shortest Path

Welcome to TheCodingCollege.com! In this tutorial, we will delve into Shortest Path Algorithms, an essential concept in Data Structures and Algorithms (DSA). These algorithms are widely used in navigation systems, network routing, and many optimization problems.

What is the Shortest Path?

In graph theory, the shortest path between two vertices is the path with the minimum total weight (or number of edges) among all possible paths connecting those vertices.

Graph Representation

  • Unweighted Graphs: The shortest path is determined by the fewest number of edges.
  • Weighted Graphs: The shortest path is based on the sum of the weights of the edges.

Types of Shortest Path Algorithms

  1. Dijkstra’s Algorithm: Works with non-negative edge weights.
  2. Bellman-Ford Algorithm: Handles graphs with negative weights.
  3. Floyd-Warshall Algorithm: Computes shortest paths between all pairs of vertices.
  4. Breadth-First Search (BFS): Used for unweighted graphs.

1. Breadth-First Search (BFS) for Unweighted Graphs

Algorithm

  1. Start from the source vertex.
  2. Use a queue to explore all neighboring vertices.
  3. Keep track of distances using an array.

Implementation in Python

from collections import deque

def bfs_shortest_path(graph, source):
    distances = {vertex: float('inf') for vertex in graph}
    distances[source] = 0
    queue = deque([source])
    
    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if distances[neighbor] == float('inf'):  # Not visited
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
    
    return distances

# Example Usage
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}
source = 0
print(bfs_shortest_path(graph, source))

2. Dijkstra’s Algorithm

Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a graph with non-negative weights.

Algorithm

  1. Use a priority queue (min-heap) to pick the vertex with the smallest distance.
  2. Update distances to neighboring vertices.
  3. Repeat until all vertices are processed.

Implementation in Python

import heapq

def dijkstra(graph, source, vertices):
    distances = {i: float('inf') for i in range(vertices)}
    distances[source] = 0
    priority_queue = [(0, source)]  # (distance, vertex)
    
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        
        if current_distance > distances[current_vertex]:
            continue
        
        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# Example Usage
graph = {
    0: [(1, 4), (2, 1)],
    1: [(3, 1)],
    2: [(1, 2), (3, 5)],
    3: []
}
source = 0
vertices = 4
print(dijkstra(graph, source, vertices))

3. Bellman-Ford Algorithm

The Bellman-Ford algorithm works for graphs with negative weights. It’s slower than Dijkstra’s algorithm but more versatile.

Algorithm

  1. Initialize distances from the source to all vertices as infinite.
  2. Relax all edges V−1V-1 times, where VV is the number of vertices.
  3. Check for negative-weight cycles in the graph.

Implementation in Python

def bellman_ford(edges, vertices, source):
    distances = [float('inf')] * vertices
    distances[source] = 0
    
    for _ in range(vertices - 1):
        for u, v, weight in edges:
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
    
    # Check for negative weight cycles
    for u, v, weight in edges:
        if distances[u] + weight < distances[v]:
            return "Graph contains a negative-weight cycle"
    
    return distances

# Example Usage
edges = [
    (0, 1, 4),
    (0, 2, 1),
    (2, 1, 2),
    (1, 3, 1),
    (2, 3, 5)
]
vertices = 4
source = 0
print(bellman_ford(edges, vertices, source))

4. Floyd-Warshall Algorithm

The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices. It uses dynamic programming to iteratively improve the distance matrix.

Algorithm

  1. Initialize the distance matrix with edge weights.
  2. Update distances considering each vertex as an intermediate point.

Implementation in Python

def floyd_warshall(graph, vertices):
    distance = [[float('inf')] * vertices for _ in range(vertices)]
    
    for i in range(vertices):
        distance[i][i] = 0
    
    for u, v, weight in graph:
        distance[u][v] = weight
    
    for k in range(vertices):
        for i in range(vertices):
            for j in range(vertices):
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
    
    return distance

# Example Usage
graph = [
    (0, 1, 4),
    (0, 2, 1),
    (1, 3, 1),
    (2, 1, 2),
    (2, 3, 5)
]
vertices = 4
print(floyd_warshall(graph, vertices))

Applications of Shortest Path Algorithms

  1. Navigation Systems: GPS and routing in maps.
  2. Network Optimization: Efficient data packet routing.
  3. Project Scheduling: Dependency management in task graphs.
  4. AI Pathfinding: Algorithms like A* for shortest path problems in games.

Comparison of Algorithms

AlgorithmGraph TypeHandles Negative WeightsTime Complexity
BFSUnweightedNoO(V+E)O(V + E)
DijkstraWeightedNoO((V+E)log⁡V)O((V + E) \log V)
Bellman-FordWeightedYesO(VE)O(VE)
Floyd-WarshallWeightedYesO(V3)O(V^3)

Conclusion

Choosing the right shortest path algorithm depends on the graph’s structure and requirements, such as the presence of negative weights or the need for all-pairs shortest paths.

Leave a Comment