Shortest Path in Undirected Graph of Unit Weights | Dijkstra + BFS | Readable C++ Code
vHiren
1870
Breadth-First SearchGraph TheoryAlgorithmInterview

You are given an Undirected Graph having unit weight of the edges, find the shortest path from src to all the vertex and if it is unreachable to reach any vertex, then return -1 for that vertex.

n = 9, m = 10
edges = [[0,1], [0,3], [3,4], [4,5], [5,6], [1,2], [2,6], [6,7], [7,8], [6,8]]
src = 0
Output: 0, 1, 2, 1, 2, 3, 3, 4, 4

Input: n = 4, m = 2
edges = [[1,3], [3,0]]
src = 3
Output: 1, 1, -1, 0

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

1 <= n, m <= 10^4
0 <= edges[i][j] <= n-1

Approach 1 : Using Dijkstra Algorithm

class Dijkstra {
    typedef pair<int, int> P;

public:
    // O(ELogV) & O(V)
    vector<int> shortestPath(vector<vector<int>>& adjList, int src) {
        int V = adjList.size();

        vector<int> minDistance(V, INT_MAX);
        minDistance[src] = 0;

        priority_queue<P, vector<P>, greater<P>> minHeap;
        minHeap.push({0, src});

        while(!minHeap.empty()) {
            auto [currDistance, node] = minHeap.top(); minHeap.pop();

            for(int neighbor : adjList[node]) {
                int newDistance = currDistance + 1;
                if(minDistance[neighbor] > newDistance) {
                    minDistance[neighbor] = newDistance;
                    minHeap.push({newDistance, neighbor});
                }
            }
        }

        for(int node = 0; node < V; ++node)
            if(minDistance[node] == INT_MAX)
                minDistance[node] = -1; // If its impossible to reach node

        return minDistance;
    }
};

Approach 2 : Using BFS

class BFS {
public:
    // O(V+E) & O(V)
    vector<int> shortestPath(vector<vector<int>>& adjList, int src) {
        int V = adjList.size();

        vector<int> minDistance(V, INT_MAX);
        minDistance[src] = 0;

        queue<int> q;
        q.push(src);

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

            for(int neighbor : adjList[node]) {
                int newDistance = minDistance[node] + 1;
                if(minDistance[neighbor] > newDistance) {
                    minDistance[neighbor] = newDistance;
                    q.push(neighbor);
                }
            }
        }

        for(int node = 0; node < V; ++node)
            if(minDistance[node] == INT_MAX)
                minDistance[node] = -1; // If its impossible to reach node

        return minDistance;
    }
};

Note: I originally solved this problem on another coding platform, and the constraints and inputs provided in this are derived from there. However, due to LeetCode guidelines, I cannot link to the original post.

𝗨𝗣𝗩𝗢𝗧𝗘 𝗜𝗙 𝗬𝗢𝗨 𝗟𝗜𝗞𝗘 𝗧𝗛𝗘 𝗦𝗢𝗟𝗨𝗧𝗜𝗢𝗡 👍

Comments (4)