The following algorithm uses Breadth-first search to find the shortest path through an unweighted graph from source node s to destination node d. The length of a path is the number of edges that it traverses

Function ShortestPath(G, s, d)

//Return the length of the shortest path from s tto d in the graph G

//Input: a graph G with properties G.node (the set of nodes in G)

//and G.edges (the set of edges in G)

//Each node n in G.node has properties:

// n.pathLength: the number of edges from n to s (set by this algorithm)

// n.neighbours: the set of adjacent nodes connected to n by one edge

//Output: the length of the shortest path from s to d

For n in G.nodes do

n.pathLength

Q Queue.empty

Q.enqueue(s)

s.pathLength

while Q.isNotEmpty do

p Q.dequeue

for u in p.neighbours do

if u.pathLength = then

u.pathLength p.pathLength + 1

Q.enqueue(u)

Return d.pathLength

a. This algorithm claims to return the shortest path from s to d, but nowhere does it compare the length of the path that it returns to any other path. Does it in fact return the shortest path? Justify your answer

b. How many times does the while loop execute when G.nodes is of size g and G.edhes

c. Consider what happens when the algorithm runs on a graph with many nodes, and is asked to find the length of the shortest path from s to s. What will the algorithm return? Is finding the shortest path from s to s faster than finding the shortest path from s to d with s d?

d. Modify the algorithm to make it mo eficient in the case where d.pathLength is found before the whole graph is explored

e. Does your modification change the asymptotic complexity of the algorithm in the average case?

f. Modify the algorithm to return not the length of the path but the path itself (i.e the sequence of nodes that leads from s to d)