LT X O file:///C:/Users/Owner/AppData/Local/Packages/Microsoft MicrosoftEdge_8wekyb3d8bbwe/Te 3%20(1).pdf ? ?? ? Problem 3. Dijkstra's Algorithm (a) Weiss, problem 9.5(a) (the problem is the same in the second and third editions). Use Dijkstras algorithm and show the results of the algorithm in the form used in lecture _a table showing for each vertex its best-known distance from the starting vertex and its predecessor vertex on the path. You can use a single table and cross-out/add values as you progress. Also write and circle the order in which the vertices are marked as visited. (b) If there is more than one minimum cost path from v to w, will Dijkstra's algorithm always find the path with the fewest edges? If not, explain in a few sentences how to modify Dijkstra's algorithm so that if there is more than one minimum path from v to w, a path with the fewest edges is chosen (c) Give an example where Dijkstra's algorithm gives the wrong answer in the presence of a negative-cost edge but no negative-cost cycles. Explain briefly why Dijkstra's algorithm fails on your example. (d) Suppose you are given a graph that has negative-cost edges but no negative-cost cycles. Consider the following strategy to find shortest paths in this graph: uniformly add a constant k to the cost of every edge, so that all costs become non-negative, then run Dijkstra's algorithm and return that result with the edge costs reverted back to their original values (i.e., with k subtracted). Give an example where this technique fails and explain why it does so. (Hint: one simple example uses only three vertices.) Also, give a general explanation as to why this technique does not work. Type here to search 56 6/26/2018 19