Purchase Solution

parent array produced by Dijkstra's algorithm

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution
Solution Summary

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

Solution Preview

It does not always work :

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

Purchase this Solution
Free BrainMass Quizzes
C# variables and classes

This quiz contains questions about C# classes and variables.

Javscript Basics

Quiz on basics of javascript programming language.

Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

Basic Networking Questions

This quiz consists of some basic networking questions.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

View More Free Quizzes
Related BrainMass Solutions

  • Dijkstra's Algorithm

    357767 Dijkstra's Algorithm Use Dijkstra's Algorithm to solve the attached question. Please provide a step by step explanation of your findings so that I may better understand this concept.

  • weighted directed graph

    algorithm Give an example of a weighted directed graph with at most 5 vertices such that Dijkstra's algorithm will NOT give the correct results for the shortest path lengths from source s to every other vertex.

  • Dijkstra's shortest path algorithm

    Dijkstra's shortest path algorithm are examined.

  • EREW parallel random-access machine algorithms

    sharedvar values : array[1..n] of nodes; blues : array[1..n] of nodes; flags : array[1..n] of boolean; mapping : array[1..n] of words; var i : word; numblues : word; parent : node; Step 1:

  • modify the Bellman-Ford algorithm

    true if (not foundCycle) print ("No negative weight cycle") printCycle(v){ //trace back in parent array to find a vertex on the cycle for u in V seen[u] = false seen[v] = true while (not seen[parent[v]]) v = parent[v] seen[v] =

  • BFS, DFS, DAGs, Topological sorting, and Dijkstra

    Since each edge and vertex is visited once, the algorithm runs in linear time. For weighted graphs, Dijkstra's algorithm delivers optimal solutions.

  • Implement Dijkstra in C++

    For the Graph in figure 16-28(a), replicate the trace of Dijkstra's algorithm to find the minimum path from vertex A to F.

  • Various Graph Theory Questions

    In solving this problem it's best to use Dijkstra's Algorithm to find the shortest distance. Dijkstra's Algorithm is as follows: 1. Assign to every node a distance value.

  • Design and Analysis of Algorithms

    We first put the numbers from the set G in an array of size m (space complexity O(m)), and create a heap out of these where parent node contains a number that is lesser than or equal to the smallest number in child nodes.

View More Related Solutions