Problem 4. We learned Dijkstra's algorithm to find the shortest paths from one source to every other node (also called one-to-all shortest paths problem), when each edge is assigned a non-negative weight. In this problem, we instead consider a different kind of graph (called a node-weighted graph) where we have weights on the nodes and not on the edges. Then the length of a path is the sum of the weights on all the nodes. The length of a path (a,b,c,d) is defined as el (a, b, c, d)) wa + 2b + wc + wd, where wa, wb, Wc and wd are the weights on nodes a, b, c and d respectively. For example, the length of the path (a,b,c,d) in the figure below is 1+2+2+1=6, and the length of the path (s, f,e) in the figure below is 0+2+3 = 5. A shortest path from a node s to t is defined as the path whose length is the shortest among all paths that start at s and end at t. (a) (3pt] Describe an algorithm (a modified version of the Dijkstra's algorithm) that takes as input a graph G = (V, E), a source node s, and weights {wi}iev and outputs the lengths of the shortest paths from s to all other nodes in V. Remark 1: This algorithm should be applicable to any graph, not just one specific example. Remark 2: There might be multiple possible methods to solve the problem. Please use a modified version of Dijkstra's algorithm. Methods like enumerating all paths will get 0 score. Hint: The description of the Dijkstra's algorithm is given in the lecture slides. You can use similar words to describe the main steps of the algorithm. (b) (5pt] Apply your algorithm to the example below to find the lengths of shortest paths from the source to all other nodes. Write your answer in a table. Remark: Your table can be a modified version of the Dijkstra's algorithm table. 0