Shortest Path Algorithms

(a) Dijkstra's algorithm for single-source shortest path on directed graphs, 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] (b) Important: read this whole question before starting it - it will save you time. Write a Java method called bellmanFord with the signature public static double [] bellmanFord (Graph g, int s) that returns an array representing the minimum distances of the nodes of g from the source node indexed by s. Your method must use the Bellman-Ford single-source shortest-path algorithm to generate its re- sult. Note, you do not have to update an array of parent nodes on the path in your code, only the array of minimum distances is required by this question. Assume the following methods are available on graphs . getEdges () which returns an array of Edge representing the edges in the graph . getNumberOfNodes which returns an integer representing the number of nodes in the graph Additionally every Edge object has the methods . getSource () which returns an integer representing the index of the source node of this edge in the graplh . getDest () which return an integer representing the index of the target node of this edge in the graph . getWeight () which returns the weight (cost) of this edge. Important: when writing your algorithm you may assume that there can be negative weight edges in g but there are no negative weight cycles in g. This means that you do not need to implement the stage of the algorithm that infects the graph beyond negative weight cycles with -oo. In your solution you must define any helper methods (be- sides those mentioned above) that you use 18 marks] (a) Dijkstra's algorithm for single-source shortest path on directed graphs, 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] (b) Important: read this whole question before starting it - it will save you time. Write a Java method called bellmanFord with the signature public static double [] bellmanFord (Graph g, int s) that returns an array representing the minimum distances of the nodes of g from the source node indexed by s. Your method must use the Bellman-Ford single-source shortest-path algorithm to generate its re- sult. Note, you do not have to update an array of parent nodes on the path in your code, only the array of minimum distances is required by this question. Assume the following methods are available on graphs . getEdges () which returns an array of Edge representing the edges in the graph . getNumberOfNodes which returns an integer representing the number of nodes in the graph Additionally every Edge object has the methods . getSource () which returns an integer representing the index of the source node of this edge in the graplh . getDest () which return an integer representing the index of the target node of this edge in the graph . getWeight () which returns the weight (cost) of this edge. Important: when writing your algorithm you may assume that there can be negative weight edges in g but there are no negative weight cycles in g. This means that you do not need to implement the stage of the algorithm that infects the graph beyond negative weight cycles with -oo. In your solution you must define any helper methods (be- sides those mentioned above) that you use 18 marks]