Professor F. Lake suggests the following algorithm for finding the shortest path from node s to node
Fantastic news! We've Found the answer you've been seeking!
Question:
Professor F. Lake suggests the following algorithm for finding the shortest path from node s to node t in a directed graph with some negative edges: add a large constant to each edge weight so that all the weights become positive, then run Dijkstra’s algorithm starting at node s, and return the shortest path found to node t. (*)
Is this a valid method? Either prove that it works correctly, or give a counterexample
Related Book For
Data Structures and Algorithms in Java
ISBN: 978-1118771334
6th edition
Authors: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
Posted Date: