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
Time Complexity:- The time complexity of an algorithm is the amount of time it requires to run to completion. Some of the reasons for studying time complexity are:- We may be in

Complexity : How do the resource needs of a program or algorithm scale (the growth of resource requirements as a function of input). In other words, what happens with the performan

Define the Internal Path Length The Internal Path Length I of an extended binary tree is explained as the sum of the lengths of the paths taken over all internal nodes- from th

The below figure illustrates the BOM (Bill of Materials) for product A. The MPS (Material requirements Planning) start row in the master production schedule for product A calls for

two standards ways of traversing a graph in data structure

This is the most extensively used internal sorting algorithm. In its fundamental form, it was invented by C.A.R. Hoare in the year of 1960. Its popularity lies in the easiness of i

A shop sells books, magazines and maps. Every item is identified by a unique 4 - digit code. All books have a code which starts with 1, all maps have a code starting with 2 and all

INSERT FUNCTION /*prototypes of insert & find functions */ list * insert_list(list *); list * find(list *, int); /*definition of  anyinsert function */ list * inser

Memory Allocation Strategies If it is not desirable to move blocks of due storage from one area of memory to another, it must be possible to relocate memory blocks that have be

The maximum degree of any vertex in a simple graph with n vertices is (n-1) is the maximum degree of the vertex in a simple graph.