Graphs with negative edge costs, Data Structure & Algorithms

We have discussed that the above Dijkstra's single source shortest-path algorithm works for graphs along with non-negative edges (like road networks). Given two scenarios can emerge out of negative cost edges into a graph:

  • Negative edge along non- negative weight cycle reachable from the source.
  • Negative edge along non-negative weight cycle reachable from source.

529_Graphs with Negative Edge costs.png

Figure: A Graph with negative edge & non-negative weight cycle

The net weight of the cycle is 2(non-negative)

437_Graphs with Negative Edge costs1.png

 Figure: A graph with negative edge and negative weight cycle

The net weight of the cycle is 3(negative) (refer to above figure). The shortest path from A to B is not well defined as the shortest path to this vertex are infinite, that means , by traveling each cycle we can reduced the cost of the shortest path by 3, like (S, A, B) is path (S, A, B, A, B) is a path with less cost and so forth.

Dijkstra's Algorithm works only for directed graphs along non-negative weights (cost).

Posted Date: 4/11/2013 4:07:40 AM | Location : United States







Related Discussions:- Graphs with negative edge costs, Assignment Help, Ask Question on Graphs with negative edge costs, Get Answer, Expert's Help, Graphs with negative edge costs Discussions

Write discussion on Graphs with negative edge costs
Your posts are moderated
Related Questions
Q. Define the graph, adjacency matrix, adjacency list, hash function, adjacency matrix, sparse matrix, reachability matrix.

Illustrate an example of algorithm Consider that an algorithm is a sequence of steps, not a program. You might use the same algorithm in different programs, or express same alg

Step 1: Choose a vertex in the graph and make it the source vertex & mark it visited. Step 2: Determine a vertex which is adjacent to the source vertex and begun a new search if

A freight train from Melbourne is approaching Sydney, carrying n cars of cargos. The cargos are to be delivered to n different cities in the metropolitan area of Sydney - one car f

Program for Linear Search. Program: Linear Search /*Program for Linear Search*/ /*Header Files*/ #include #include /*Global Variables*/ int search; int

Differentiate between Nonpersistent and 1-persistent Nonpersistent: If the medium is idle, transmit; if the medium is busy, wait an amount of time drawn from a probability dist

a) Given a digraph G = (V,E), prove that if we add a constant k to the length of every arc coming out from the root node r, the shortest path tree remains the same. Do this by usin

Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the

Tree is dynamic data structures. Trees can expand & contract as the program executes and are implemented via pointers. A tree deallocates memory whereas an element is deleted.

What is an unreachable code assertion An unreachable code assertion can be placed at the default case; if it's every executed, then program is in an erroneous state. A loop in