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.

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

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

 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

Ask an Expert

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

Write your message here..

Related Questions

Explain the array and linked list implementation of stack, Question 1. ... 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, How do you find the complex... 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 required to evaluate a postfix expression, The data stru... The data structure needed to evaluate a postfix expression is  Stack

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

Size of stack, The size of stack was declared as ten. Thus, stack cannot ho... 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, What is Ruby Ruby has numerous simple types, including nu... 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,

Algorithms, Data array A has data series from 1,000,000 to 1 with step size... 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.

Data mining assignment, The assignment aims at consolidating your knowledge... 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

Generic doubly linked list, Your objective is to write a generic doubly lin... 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

Perform depth -first search, You are given two jugs, a 4-gallon one and a 3... 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