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
Question 1. How can you find out the end of a String? Write an algorithm to find out the substring of a string. 2. Explain the insertion and deletion operation of linked lis

How do you find the complexity of an algorithm?  Complexity of an algorithm is the measure of analysis of algorithm. Analyzing an algorithm means predicting the resources that

The data structure needed to evaluate a postfix expression is  Stack

Q. Write down the binary search algorithm and trace to search element 91 in following given list: 13          30          62           73         81         88             91

The size of stack was declared as ten. Thus, stack cannot hold more than ten elements. The major operations which can be performed onto a stack are push and pop. However, in a prog

What is Ruby Ruby has numerous simple types, including numeric classes such as Integer, Fixnum, Bignum, Float, Big Decimal, Rational, and Complex, textual classes like String,

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

The assignment aims at consolidating your knowledge on data mining techniques and developing practical skills through solving a problem of transcription factor binding sites recogn

Your objective is to write a generic doubly linked list class called CS228LinkedList that implements the List interface and uses a type variable T. All methods except for subList a

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring marker on it. There is a tap that can be used to fill the jugs with water. How can you get exac