Shortest Path Algorithms

(a) Breadth-first search (BFS) can be used to perform single source short- est paths on anv graph where all edges have the same weights. Write an algorithm using BFS to assign distances to all nodes in a graph and give the time complexity of this algorithm. [7 marks] Dijkstra's algorithm for single-source shortest path on directed graph as given in lectures, assumed a heap-based priority queue was used to store tentative unscanned node distances. However, the original version of Dijkstra's algorithm used an array to store these distances Give the time complexity of this original version of Dijkstra's algorithm taking account of the cost of array access. Give a brief explanation of your answer. [5 marks] (c) Consider the following graph 10 8 4 Solve the single-source-shortest path problem for the start node vi using Dijkstra's algorithm. List for each iteration which nodes becomes scanned and which edges are relaxed [12 marks] (d) Briefly explain, with the use of an example, why Dijkstra's algorithm will not work on graphs with negative weight edges [4 marks]