a$)$ Prove that by using Fibonacci heap, the Dijkstra's algorithm has a time complexity of

$O(E+$VlogV$).$ If sqrt$(V,$ will using Fibonacci heap be the best option?

b$)$ Breadth$-$first search, Dijkstra's algorithm, the Bellman$-$Ford algorithm, and the Floyd$-$

Warshall algorithm can all be utilized to find the shortest paths in a graph. Match each

question with the most appropriate answer.

When would you choose breadth$-$first search

over Dijkstra's algorithm?

When would you choose Floyd$-$Warshall over

Bellman$-$Ford?

When would you choose Bellman$-$Ford over

Dijkstra's algorithm?

When you want to find the shortest paths

between all pairs of vertices.

When you want to find the shortest paths

from a specific vertex $s$ to any other vertex $t$

When the graph is unweighted.

When the graph has negative edge weights.