Explore BrainMass

Explore BrainMass

    parent array produced by Dijkstra's algorithm

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Here is a proposed algorithm to solve the single source shortest paths problem in a weighted directed graph G with possibly negative edges weights, but no negative weight cycles:
    Form the graph G' from G by adding the same positive number, p, to all of the edge weights in the graph. This positive number should be chosen so that all the edge weights in G' are positive. (p = 1 + | min edge weight in G|). Run Dijkstra's algorithm on G'.

    Is it true that the parent array produced by Dijkstra's algorithm on G' will also give the shortest paths in the original graph, G? Justify your answer with a counterexample or a sketch of a correctness proof.

    © BrainMass Inc. brainmass.com March 6, 2023, 1:23 pm ad1c9bdddf

    Solution Preview

    It does not always work :

    Consider a graph with 5 vertices, A, B, C, D and ...

    Solution Summary

    A parent array produced by Dijkstra's algorithm is debated.