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

Hash function, Q. Define the graph, adjacency matrix, adjacency list, hash ... Q. Define the graph, adjacency matrix, adjacency list, hash function, adjacency matrix, sparse matrix, reachability matrix.

Illustrate an example of algorithm, Illustrate an example of algorithm ... 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

Algorithm for dfs, Step 1: Choose a vertex in the graph and make it the sou... 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

Train reorganising, A freight train from Melbourne is approaching Sydney, c... 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 for Linear Search. Program: Linear S... 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, Differentiate between... 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

Relationship between shortest path distances of modified, a) Given a digrap... 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

Program on radix sort., Write a program that uses the radix sort to sort 10... 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

Data structure- tree, Tree is dynamic data structures. Trees can expand & c... 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, What is an unreachable code assertio... 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