Question

Explain how to find a path with the least number of edges between two vertices in an undirected graph by considering it as a shortest path problem in a weighted graph.

Short answer

Set the weights for the given graph as \(1\), to obtain a weighted graph and apply any method to find the shortest path between vertices.

Step-by-step solution

Given data

A connected graph, for which the problem of finding the paths with the least number of edges has to be solved.

Concept used of Dijkstra’s algorithm

Dijkstra's algorithm allows us to find the shortest path between any two vertices of a graph.

Find the path

Assume we know a procedure \(P\), say how to find the shortest paths between vertices in a weighted graph, for example, by using Dijkstra's algorithm.

We are given a connected graph and want to find the paths between a given pair of vertices having the least number of edges. In order to solve this using, the procedure \(P\) proceed as follows to each edge in the given graph, assign the weight \(1\).

Now, we have a weighted graph, for which the procedure \(P\) can be applied.

Note that the shortest path between any pair of vertices is just the least number of edges between them, as the weights of edges are all \(1\). In this way, we have solved the required problem of finding the least number of edges between vertices using a method of finding shortest paths between vertices.