Let G$=($V$,$E$,$w$)$

be a simple weighted digraph with n

vertices and m

edges, and non$-$negative edge weights. Let s in V

be a selected source. We want to rank the vertices from $1$ to n

based on how close they are to the source vertex, where closeness of a vertex is measured in terms of its shortest path distance from the source. So$,$ vertex s

has rank $1.$ The problem is to find the rank k

vertex for a given integer k in $[1..$n$]$

$.$ This problem can be solved efficiently by

Question $8$Answer

a$.$

doing a BFS and stopping at level k

$.$

b$.$

restricting Bellman$-$Ford's algorithm to k

iterations of its main loop.

c$.$

restricting Dijkstra's algorithm to k

iterations of its main loop.

d$.$

restricting Floyd$-$Warshall's algorithm to k

iterations of its main loop.