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
Q1. Define a sparse matrix. Explain different types of sparse matrices? Evaluate the method to calculate address of any element a jk of a matrix stored in memory. Q2. A linear

Open addressing The easiest way to resolve a collision is to start with the hash address and do a sequential search by the table for an empty location.

Q. Give the algorithm to build a binary tree where the yields of preorder and post order traversal are given to us.

what is multilist length file organisation? explain with an example

How does cpu''s part tming and controls generate and controls signls in computer?

Which sorting methods would be most suitable for sorting a list which is almost sorted  Bubble Sorting method.

Implementation of queue using a singly linked list: While implementing a queue as a single liked list, a queue q consists of a list and two pointers, q.front and q.rear.

implement multiple stacks in an array and write different algorithms to perform operations on it

Q. Describe the adjacency matrix and make the same for the given undirected graph.    Ans: The representation of Adjacency Matrix: This representation consists of

Define Merge Sort  Merge sort is a perfect example of a successful application of the divide and conquer method. It sorts a given array A[0...n-l] by separating it into two ha