Shortest Path Finding

Shortest Path Finding

The Shortest Path Finding problem involves finding the path between two nodes in a graph such that the sum of the weights (or costs) of the edges in the path is minimized. The problem can be solved using different algorithms depending on the type of graph (directed/undirected), edge weights (positive/negative), and other factors like the graph's density.

Types of Graphs and Algorithms

1. Weighted Graphs (Edges have weights):

   • Dijkstra's Algorithm (for non-negative edge weights)
   • Bellman-Ford Algorithm (handles negative edge weights but not negative cycles)
   • Floyd-Warshall Algorithm (finds shortest paths between all pairs of vertices)

2. Unweighted Graphs:

   • Breadth-First Search (BFS) (used for finding the shortest path in unweighted graphs)

We will focus on Dijkstra's Algorithm and Bellman-Ford Algorithm as they are the most commonly used algorithms for shortest path problems involving weighted graphs.

1. Dijkstra's Algorithm

Dijkstra's Algorithm is a greedy algorithm used to find the shortest path from a single source node to all other nodes in a graph with non-negative edge weights.

Key Features:

• Works on:

  • Directed or undirected graphs.
  • Graphs with non-negative weights (i.e., no negative weight edges).

• Idea: Start from the source node, repeatedly pick the node with the smallest tentative distance, and update its neighbors' tentative distances. This process continues until all nodes are processed.

Steps to Solve Using Dijkstra's Algorithm:

1. Initialization:

   • Set the distance to the source node as 0 and the distance to all other nodes as infinity.
   • Mark all nodes as unvisited.

2. Main Loop:

   • Select the node with the smallest tentative distance (initially the source).
   • For each neighbor of this node, calculate the tentative distance (current node’s distance + edge weight).
   • If this new distance is smaller than the previously recorded distance, update the shortest distance for that neighbor.

3. Repeat until all nodes are visited.

Time Complexity:

• Using a simple array: O(V²) where V is the number of vertices.
• Using a priority queue (min-heap): O((V + E) log V) where V is the number of vertices and E is the number of edges.

C++ Implementation of Dijkstra's Algorithm:

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// Define a structure to represent an edge
struct Edge {
    int dest;
    int weight;
};

// Define a structure to represent a node in the priority queue
struct Node {
    int vertex;
    int distance;
    bool operator>(const Node& other) const {
        return distance > other.distance;
    }
};

// Function to implement Dijkstra's Algorithm
void dijkstra(int V, vector<vector<Edge>>& adjList, int source) {
    // Vector to store the shortest distance from the source to each vertex
    vector<int> dist(V, INT_MAX);
    dist[source] = 0;

    // Min-heap priority queue to store vertices along with their tentative distances
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({source, 0});
    
    while (!pq.empty()) {
        // Get the vertex with the minimum distance
        Node u = pq.top();
        pq.pop();
        
        // Explore all neighbors of the current vertex
        for (auto& edge : adjList[u.vertex]) {
            int v = edge.dest;
            int weight = edge.weight;

            // If the new distance is smaller, update it and push the neighbor into the queue
            if (dist[u.vertex] + weight < dist[v]) {
                dist[v] = dist[u.vertex] + weight;
                pq.push({v, dist[v]});
            }
        }
    }

    // Print the shortest distance to each vertex
    for (int i = 0; i < V; i++) {
        cout << "Distance from source to vertex " << i << ": " << dist[i] << endl;
    }
}

int main() {
    int V = 5;  // Number of vertices
    vector<vector<Edge>> adjList(V);
    
    // Add edges (vertex, weight)
    adjList[0].push_back({1, 10});
    adjList[0].push_back({2, 5});
    adjList[1].push_back({2, 2});
    adjList[1].push_back({3, 1});
    adjList[2].push_back({1, 3});
    adjList[2].push_back({3, 9});
    adjList[2].push_back({4, 2});
    adjList[3].push_back({4, 4});
    adjList[4].push_back({0, 7});
    adjList[4].push_back({3, 6});

    int source = 0;  // Source node
    dijkstra(V, adjList, source);
    
    return 0;
}

Explanation of Code:

1. Graph Representation: We use an adjacency list adjList where each node contains a list of edges (Edge structure) pointing to its neighboring nodes.
2. Priority Queue: We use a priority queue (min-heap) to always extract the node with the smallest tentative distance.
3. Relaxation: The algorithm relaxes edges, meaning it checks whether a shorter path to a neighbor can be found by going through the current node. If so, the distance is updated.

Example Output:

For the graph in the example, if we set the source as 0, the output will show the shortest distances from node 0 to all other nodes.

2. Bellman-Ford Algorithm

Bellman-Ford Algorithm is another algorithm to find the shortest paths from a single source node to all other nodes, but unlike Dijkstra's algorithm, it can handle negative weight edges. However, it cannot handle negative weight cycles (cycles where the sum of the weights is negative).

Steps to Solve Using Bellman-Ford:

1. Initialization:

   • Set the distance to the source node as 0 and all other nodes as infinity.

2. Relaxation:

   • For each edge (u, v) with weight w, if the distance to v via u is smaller than the current known distance, update the distance to v.
   • Repeat this process for all edges for V-1 iterations, where V is the number of vertices.

3. Check for Negative Weight Cycles:

   • After V-1 iterations, if there is any edge (u, v) such that dist[u] + weight < dist[v], then a negative weight cycle exists.

Time Complexity:

• Time Complexity: O(V * E) where V is the number of vertices and E is the number of edges. This is because we perform relaxation V-1 times over all edges.
• Space Complexity: O(V) for storing the distances.

C++ Implementation of Bellman-Ford Algorithm:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// Define a structure to represent an edge
struct Edge {
    int u, v, weight;
};

// Function to implement Bellman-Ford Algorithm
void bellmanFord(int V, vector<Edge>& edges, int source) {
    vector<int> dist(V, INT_MAX);
    dist[source] = 0;

    // Relax all edges (V-1) times
    for (int i = 1; i < V; ++i) {
        for (auto& edge : edges) {
            if (dist[edge.u] != INT_MAX && dist[edge.u] + edge.weight < dist[edge.v]) {
                dist[edge.v] = dist[edge.u] + edge.weight;
            }
        }
    }

    // Check for negative weight cycles
    for (auto& edge : edges) {
        if (dist[edge.u] != INT_MAX && dist[edge.u] + edge.weight < dist[edge.v]) {
            cout << "Graph contains negative weight cycle!" << endl;
            return;
        }
    }

    // Print the shortest distances
    for (int i = 0; i < V; ++i) {
        cout << "Distance from source to vertex " << i << ": " << dist[i] << endl;
    }
}

int main() {
    int V = 5; // Number of vertices
    vector<Edge> edges = {
        {0, 1, -1}, {0, 2, 4}, {1, 2, 3}, {1, 3, 2}, {1, 4, 2},
        {2, 3, 5}, {2, 4, 1}, {3, 4, -3}
    };

    int source = 0; // Source node
    bellmanFord(V, edges, source);
    
    return 0;
}

Explanation of Code:

1. Graph Representation: The graph is represented by a list of edges where each edge has a start vertex u, an end vertex v, and a weight.
2. Relaxation