Shortest Path in Weighted undirected graph

You are given a weighted undirected graph having n vertices numbered from 1 to n and m edges along with their weights. Find the shortest path between the vertex 1 and the vertex n,  if there exists a path, and returna list of integers whose first element is the weight of the path, and the rest consist of the nodes on that path. If no path exists, then return a list containing a single element -1.

The input list of edges is as follows – {a, b, w}, denoting there is an edge between a and b, and w is the weight of that edge.

Note: The driver code here will first check if the weight of the path returned is equal to the sum of the weights along the nodes on that path, if equal it will output the weight of the path, else -2. In case the list contains only a single element (-1) it will simply output -1. 

Examples :

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: 5
Explanation: Shortest path from 1 to n is by the path 1 4 3 5 whose weight is 5. 

Input: n = 2, m= 1, edges = [[1, 2, 2]]
Output: 2
Explanation: Shortest path from 1 to 2 is by the path 1 2 whose weight is 2. 

Input: n = 2, m= 0, edges = [ ]
Output: -1
Explanation: Since there are no edges, so no answer is possible.

Expected Time Complexity: O(m* log(n))
Expected Space Complexity: O(n+m)

Constraint:
2 <= n <= 10⁶
0 <= m <= 10⁶
1 <= a, b <= n
1 <= w <= 10⁵

Approach 01:

#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> shortestPath(int numNodes, int numEdges, vector<vector<int>>& edges) {
        // Create adjacency list for the graph
        vector<pair<int, int>> adj[numNodes + 1];
        for (auto edge : edges) {
            adj[edge[0]].push_back({edge[1], edge[2]});
            adj[edge[1]].push_back({edge[0], edge[2]});
        }

        // Priority queue to store {distance, node}
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, 1});

        // Distance vector to store shortest distance to each node, initialized to INT_MAX
        vector<int> distance(numNodes + 1, INT_MAX);

        // Parent vector to store the path
        vector<int> parent(numNodes + 1);

        // Initialize the distance to the start node and set parents
        for (int i = 1; i <= numNodes; i++) {
            parent[i] = i;
        }
        distance[1] = 0;

        // Dijkstra's algorithm
        while (!pq.empty()) {
            auto topElement = pq.top();
            int currentNode = topElement.second;
            int currentDistance = topElement.first;
            pq.pop();

            // Iterate through the adjacent nodes
            for (auto adjacent : adj[currentNode]) {
                int adjNode = adjacent.first;
                int weight = adjacent.second;

                // If a shorter path is found
                if (currentDistance + weight < distance[adjNode]) {
                    distance[adjNode] = currentDistance + weight;
                    pq.push({currentDistance + weight, adjNode});
                    parent[adjNode] = currentNode;
                }
            }
        }

        // If there is no path to the destination node
        if (distance[numNodes] == INT_MAX) return {-1};

        // Construct the shortest path
        vector<int> path;
        int currentNode = numNodes;
        while (parent[currentNode] != currentNode) {
            path.push_back(currentNode);
            currentNode = parent[currentNode];
        }
        path.push_back(1);
        path.push_back(distance[numNodes]); // Append the shortest distance to the path
        reverse(path.begin(), path.end());

        return path;
    }
};

import heapq
from typing import List, Tuple

class Solution:
    def shortestPath(self, numNodes: int, numEdges: int, edges: List[List[int]]) -> List[int]:
        # Create adjacency list for the graph
        adj = [[] for _ in range(numNodes + 1)]
        for edge in edges:
            adj[edge[0]].append((edge[1], edge[2]))
            adj[edge[1]].append((edge[0], edge[2]))
        
        # Priority queue to store (distance, node)
        pq = [(0, 1)]  # Start from node 1 with distance 0
        
        # Distance list to store shortest distance to each node, initialized to infinity
        distance = [float('inf')] * (numNodes + 1)
        
        # Parent list to store the path
        parent = [0] * (numNodes + 1)
        
        # Initialize the distance to the start node and set parents
        for i in range(1, numNodes + 1):
            parent[i] = i
        distance[1] = 0
        
        # Dijkstra's algorithm
        while pq:
            currentDistance, currentNode = heapq.heappop(pq)
            
            # If current distance is greater than stored distance, skip
            if currentDistance > distance[currentNode]:
                continue
            
            # Iterate through the adjacent nodes
            for adjNode, weight in adj[currentNode]:
                # Calculate new distance
                newDistance = currentDistance + weight
                
                # If a shorter path is found
                if newDistance < distance[adjNode]:
                    distance[adjNode] = newDistance
                    heapq.heappush(pq, (newDistance, adjNode))
                    parent[adjNode] = currentNode
        
        # If there is no path to the destination node
        if distance[numNodes] == float('inf'):
            return [-1]
        
        # Construct the shortest path
        path = []
        currentNode = numNodes
        while parent[currentNode] != currentNode:
            path.append(currentNode)
            currentNode = parent[currentNode]
        path.append(1)
        path.append(distance[numNodes])  # Append the shortest distance to the path
        path.reverse()
        
        return path

Time Complexity

• Adjacency List Construction:

  Constructing the adjacency list from the given edges takes \( O(E) \) time, where \( E \) is the number of edges.

• Dijkstra’s Algorithm:

  The main part of the algorithm involves processing each edge and node once, and each insertion and deletion from the priority queue takes \( O(\log V) \) time, where \( V \) is the number of vertices. Therefore, the time complexity of Dijkstra’s algorithm is \( O((V + E) \log V) \).

• Constructing the Shortest Path:

  Constructing the shortest path involves tracing back from the destination node to the start node, which takes \( O(V) \) time in the worst case.

• Overall Time Complexity:

  The overall time complexity is dominated by Dijkstra’s algorithm, resulting in \( O((V + E) \log V) \).

Space Complexity

• Adjacency List:

  The adjacency list requires \( O(V + E) \) space to store all the edges and vertices.

• Priority Queue:

  The priority queue can store up to \( O(V) \) elements in the worst case, resulting in \( O(V) \) space complexity.

• Distance and Parent Arrays:

  Arrays like distance and parent each require \( O(V) \) space.

• Overall Space Complexity:

  Considering the adjacency list and other auxiliary arrays, the overall space complexity is \( O(V + E) \).