Consider the graph below: Which of the following is needed to properly run the D
ID: 3754801 • Letter: C
Question
Consider the graph below: Which of the following is needed to properly run the Djkstra algorithm? (Select all that are needed) Positive weights of all ordered pairs: w(A,B), w(A,C), w(A,D), W(A,E), w(B,C), w(B,D), w(B,E), w(C,D), w(C,E), w(D,E The contents of the temporary set T O Positive weights of edges: w(A,B), w(A,C), w(B,C), w(C,D), w(B,E), w(D,E) Cost labels of all nodes. Negative or positive weights of all ordered pairs: w(A,B), w(A,C), w(A,D), w(A,E), w(B,C), w(B,D), w(B,E), w(C,D), w(C,E), w(D,E) Cost label of the final node such as D Initial node such as A Final node such as D Negative or positive weights of edges: w(A,B), w(A,C), w(B,C), w(C,D), w(B,E), w(D,E)Explanation / Answer
(A) NOT NEEDED. Here few of the edges are not part of the graph so their weights are not required.
(B) NEEDED. This is the set of the unvisited vertices and this is required for the algorithm.
(C) NEEDED. Dijkstra algorithm works on nonnegative edge weights only and since all these pairs are edges in the graph, they are required.
(D) NOT NEEDED. Cost of the edges are required and not the nodes/vertices.
(E) NOT NEEDED. Same as (A). Moreover the weights must be non negative.
(F) NOT NEEDED. No cost of nodes are required, only the edge weights needed.
(G) NEEDED. Source node where are Dijkstra's algorithm will begin is needed.
(H) NOT NEEDED. Dijkstra's algorithm calculates shortest distance from a single node to all other nodes in the graph. FInal node is not needed in this case.
(I) NOT NEEDED. Dijkstra's algorithm works with positive weight edges only.