> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/find-the-shortest-path-between-two-vertices-in-an-undirected-graph.md).

# Find the shortest path between two vertices in an undirected graph

Program to find the shortest path between two vertices in an undirected graph is discussed here. Given a graph, find the shortest path between the given source and destination nodes.

For example, consider the graph given below. We have to find the shortest path between vertices 1 and 5.

![shortest path between two vertices in a graph](https://i1.faceprep.in/Companies-1/shortest%20path%20between%20two%20vertices%20in%20a%20graph.png)

1 -> 0 -> 4 -> 5

1 -> 0 -> 2 -> 5

1 -> 2 -> 5

**Shortest path: 1 -> 2 -> 5**

**Number of edges: 2**

```java
public class Solution {
    public static ArrayList<Integer> getPathBFSHelper(int[][] edges, int sv, int ev, boolean[] visited) {
        int n = edges.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        if (sv == ev) {
            ArrayList<Integer> ans = new ArrayList<>();
            ans.add(sv);
            return ans;
        }
        queue.add(sv);
        visited[sv] = true;
        while (!queue.isEmpty()) {
            int front = queue.remove();
            for (int i = 0; i < n; i++) {
                if (edges[front][i] == 1 && !visited[i]) {
                    map.put(i, front);
                    queue.add(i);
                    visited[i] = true;
                    if (i == ev) {
                        ArrayList<Integer> ans = new ArrayList<>();
                        ans.add(ev);
                        int value = map.get(ev);
                        while (value != sv) {
                            ans.add(value);
                            value = map.get(value);
                        }
                        ans.add(value);
                        return ans;
                    }
                }
            }
        }
        return null;
    }

    public static ArrayList<Integer> getPathBFS(int[][] edges, int sv, int ev) {
        boolean[] visited = new boolean[edges.length];
        return getPathBFSHelper(edges, sv, ev, visited);
    }
}
```