Shortest path in Undirected Graph

JavaView on GFG

Time: O(V+E)

Space: O(V)

Intuition

BFS on unweighted graph gives shortest path in terms of edge count.

Algorithm

1BFS from source. dist[] = -1 initially. dist[src]=0.
2BFS level by level. Return dist[].

Common Pitfalls

•BFS guarantees shortest path in unweighted graph. Returns -1 for unreachable nodes.

Shortest path in Undirected Graph.java

Java

// Approach: BFS from source. BFS guarantees shortest path in unweighted graphs.
// Time: O(V+E) Space: O(V)
import java.util.*;

class Solution {

    public int[] shortestPath(int[][] edges, int n, int m, int src) {
        List<List<Integer>> adjList = new ArrayList<>();

        for (int i = 0; i < n; i++)
            adjList.add(new ArrayList<>());

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adjList.get(u).add(v);
            adjList.get(v).add(u);
        }

        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[src] = 0;

        Queue<Integer> q = new LinkedList<>();
        q.add(src);

        while (!q.isEmpty()) {
            int node = q.poll();

            for (int adjNode : adjList.get(node)) {
                if (dist[adjNode] == -1) {
                    dist[adjNode] = dist[node] + 1;
                    q.add(adjNode);
                }
            }
        }

        return dist;
    }
}

Was this solution helpful?