Shortest Path

Shortest Path in Graphs

The shortest path problem involves finding the minimum distance or minimum number of edges between two vertices in a graph. Depending on the graph type (weighted or unweighted) and other constraints, there are different algorithms to solve this problem.

Key Concepts

1. Weighted Graph: Edges have weights (costs).
2. Unweighted Graph: All edges have the same weight (often $1$).
3. Shortest Path: Path with the smallest total weight or minimum number of edges.

Algorithms for Shortest Path

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

• Works only on unweighted graphs.
• Finds the shortest path in terms of the number of edges.

Steps:

1. Use a queue to explore the graph level by level.
2. Start from the source vertex and mark it as visited.
3. Track the distance of each vertex from the source.

Code in C++:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfsShortestPath(int src, int V, vector<vector<int>> &adj) {
    vector<int> distance(V, -1); // Distance array initialized to -1
    queue<int> q;

    distance[src] = 0; // Distance to source is 0
    q.push(src);

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        for (int neighbor : adj[current]) {
            if (distance[neighbor] == -1) { // Not visited
                distance[neighbor] = distance[current] + 1;
                q.push(neighbor);
            }
        }
    }

    // Print distances
    cout << "Shortest distances from source " << src << ":" << endl;
    for (int i = 0; i < V; i++) {
        cout << "Vertex " << i << ": " << distance[i] << endl;
    }
}

int main() {
    int V = 6; // Number of vertices
    vector<vector<int>> adj(V);

    // Add edges to the adjacency list
    adj[0] = {1, 2};
    adj[1] = {0, 3, 4};
    adj[2] = {0, 4};
    adj[3] = {1, 5};
    adj[4] = {1, 2, 5};
    adj[5] = {3, 4};

    bfsShortestPath(0, V, adj);

    return 0;
}

Output:

Shortest distances from source 0:
Vertex 0: 0
Vertex 1: 1
Vertex 2: 1
Vertex 3: 2
Vertex 4: 2
Vertex 5: 3

2. Dijkstra's Algorithm for Weighted Graphs

• Finds the shortest path from a source vertex to all other vertices in a non-negative weighted graph.

Steps:

1. Use a priority queue to always explore the vertex with the smallest known distance.
2. Update the distances of neighboring vertices if a shorter path is found.

Code in C++:

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

void dijkstra(int src, int V, vector<vector<pair<int, int>>> &adj) {
    vector<int> distance(V, INT_MAX); // Initialize distances to infinity
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    distance[src] = 0; // Distance to source is 0
    pq.push({0, src}); // {distance, vertex}

    while (!pq.empty()) {
        int dist = pq.top().first;
        int current = pq.top().second;
        pq.pop();

        for (auto neighbor : adj[current]) {
            int nextVertex = neighbor.first;
            int edgeWeight = neighbor.second;

            if (distance[current] + edgeWeight < distance[nextVertex]) {
                distance[nextVertex] = distance[current] + edgeWeight;
                pq.push({distance[nextVertex], nextVertex});
            }
        }
    }

    // Print distances
    cout << "Shortest distances from source " << src << ":" << endl;
    for (int i = 0; i < V; i++) {
        cout << "Vertex " << i << ": " << distance[i] << endl;
    }
}

int main() {
    int V = 5; // Number of vertices
    vector<vector<pair<int, int>>> adj(V);

    // Add edges to the adjacency list
    adj[0] = {{1, 2}, {2, 4}};
    adj[1] = {{2, 1}, {3, 7}};
    adj[2] = {{3, 3}, {4, 5}};
    adj[3] = {{4, 1}};
    adj[4] = {};

    dijkstra(0, V, adj);

    return 0;
}

Output:

Shortest distances from source 0:
Vertex 0: 0
Vertex 1: 2
Vertex 2: 3
Vertex 3: 6
Vertex 4: 7

3. Bellman-Ford Algorithm for Weighted Graphs

• Handles graphs with negative weights.
• Slower than Dijkstra’s algorithm but more versatile.

Steps:

1. Initialize distances from the source to infinity.
2. Relax all edges $V-1$ times.
3. Check for negative weight cycles.

4. Floyd-Warshall Algorithm

• Finds the shortest path between all pairs of vertices.
• Uses dynamic programming.

Comparison of Algorithms