Question

Fastest algorithm for computing a shortest (miniμm hop-length) path in an (unweighted) digraph from u to v, for one given pair of vertices u and v.

a) Dijkstra's algorithm
b) Breadth-first search
c) Depth-first search
d) Floyd-Warshall algorithm

Answer 1

The fastest algorithm for computing a shortest path in an unweighted digraph is the Breadth-first search (BFS) algorithm, while Dijkstra's algorithm is more suitable for graphs with weighted edges.

Step-by-step explanation:

The fastest algorithm for computing a shortest (minimum hop-length) path in an (unweighted) digraph from u to v, for one given pair of vertices u and v, is the Breadth-first search (BFS) algorithm.

BFS explores all the vertices of the graph in a level-by-level manner, starting from the source vertex. It visits all the adjacent vertices of a vertex before moving to the next level. This way, it ensures that the shortest path is found.

Dijkstra's algorithm is also an option, but it is more suitable for graphs with weighted edges. Depth-first search (DFS) and Floyd-Warshall algorithm are not efficient for finding the shortest path in unweighted graphs.