In a connected non-weighted graph, the Breadth-First Traversal algorithm (BFS) can be used to find the shortest distance between the source vertex and every other vertex by adding only a couple of lines. Here is a reproduction of the BFS algorithm :

Algorithm BFS (x) initialize Q visit[x] = true Q.insert(x) while not empty Q do v = Q.dequeue() for each unvisited neighbour w of v do visit[w] = true Q.insert(w) 

Show how to introduce a simple modification in the algorithm to find the shortest distance (i.e. number of edges) between vertex x and every other vertex; What is the time complexity of your algorithm, given that the Graph has n vertices and m edges?