DAY 40 - Shortest Path in Weighted undirected graph

Hey everyone! Welcome back to another day of problem-solving. It's day 40, and I'm still going strong on my quest for consistency. Today, we will be doing a continuation of our last problem the change being the graph is weighted now.

Question: Shortest Path in Weighted undirected graph

You are given a weighted undirected graph having n vertices numbered from 1 to n and m edges describing there are edges between a to b with some weight, find the shortest path between the vertex 1 and the vertex n and if path does not exist then return a list consisting of only -1.

Example 1:

Input:
n = 5, m= 6
edges = [[1,2,2], [2,5,5], [2,3,4], [1,4,1],[4,3,3],[3,5,1]]
Output:
1 4 3 5
Explanation:
Shortest path from 1 to n is by the path 1 4 3 5

Constraints:

- Constraint:
- 2 <= n <= 105
- 0 <= m <= 105
- 0<= a, b <= n
- 1 <= w <= 105

Intuition:

We will be using the Dijkstra's algorithm to solve this question. It's a classic algorithm , I suggest reading out an article on it understand it better. It can be implemented using priority queue, set etc. I have linked the articles below. It is recommended to read them before reading the algorithm for the solution

We will use an array called ‘parent’ for the purpose that it would store the parent node for each node and will update itself if a shorter path from a node is found at some point in time. This will help us to print the path easily at the end by backtracking through the parent array till we reach the source node.

We will be using a priority queue based min heap approach.

• Dijkstra's Algorithm Introduction

• Dijkstra's Algorithm Using Priority Queue

Algorithm:

1. Creating the Adjacency List:

• We start by creating the adjacency list representation of the graph.
• We iterate over the given edges and extract the source vertex (u), destination vertex (v), and edge weight (wt).
• For each edge, we add v to the adjacency list of u with the corresponding weight, and vice versa, since the graph is undirected.

1. Initializing Variables:

• We initialize a priority queue called pq to store vertices based on their distance from the source vertex.
• We also create a distance array, dist, to keep track of the shortest distances from vertex 1 to all other vertices.
• Initially, all distances are set to a large value (1e9) to represent infinity, except for the source vertex (1), which is set to 0.
• Additionally, we create a parent array to keep track of the parent of each vertex in the shortest path.

1. Applying Dijkstra's Algorithm:

• We use Dijkstra's algorithm to find the shortest path.
• We enqueue the source vertex (1) with a distance of 0 to start the process.
• While the priority queue is not empty, we dequeue a vertex with the smallest distance.
• For each adjacent vertex of the dequeued vertex, we calculate the new distance by adding the edge weight and the current distance.
• If the new distance is smaller than the current distance, we update the distance, enqueue the vertex with the new distance, and update its parent in the parent array.

1. Checking Reachability:

• If the distance to the destination vertex (n) remains unchanged (1e9) after applying Dijkstra's algorithm, it means that the destination vertex is unreachable from the source vertex.
• In such a case, we return [-1] to indicate that there is no path.

1. Constructing the Shortest Path:

• If the destination vertex is reachable, we construct the shortest path using the parent array.
• We start from the destination vertex (n) and follow the parent pointers until we reach the source vertex (1).
• During this process, we store the vertices in the path vector.
• Finally, we reverse the path vector to obtain the correct order of vertices from source to destination and return it as the result.

Code:

vector<int> shortestPath(int n, int m, vector<vector<int>>& edges) {
    // Step 1: Creating the Adjacency List
    vector<pair<int,int>> adj[n+1];
    for(auto it : edges){
        int u = it[0];
        int v = it[1];
        int wt = it[2];
        adj[u].push_back({v,wt});
        adj[v].push_back({u,wt});
    }

    // Step 2: Initializing Variables
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> dist(n+1,1e9);
    dist[1] = 0;
    vector<int> parent(n+1);
    for(int i = 1; i < parent.size(); i++){
        parent[i] = i;
    }
    pq.push({0,1});

    // Step 3: Applying Dijkstra's Algorithm
    while(!pq.empty()){
        int node = pq.top().second;
        int dis = pq.top().first;
        pq.pop();

        for(auto it : adj[node]){
            int adjNode = it.first;
            int edgeWeight  = it.second;

            // Update the distance if a shorter path is found
            if(dis + edgeWeight < dist[adjNode]){
                dist[adjNode] = dis + edgeWeight;
                pq.push({dis + edgeWeight,adjNode});
                parent[adjNode] = node;
            }
        }
    }

    // Step 4: Checking Reachability
    if(dist[n] == 1e9){
        return {-1}; // Destination vertex is unreachable
    }

    // Step 5: Constructing the Shortest Path
    vector<int> path;
    int node = n;
    while(parent[node] != node){
        path.push_back(node);
        node = parent[node];
    }

    path.push_back(1);
    reverse(path.begin(),path.end());
    return path; // Return the shortest path from source to destination
}

Complexity Analysis:

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

Feel free to let me know if you have any questions or need further clarification. Happy problem-solving!