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 time complexity, Time Complexity:- The time complexity of an algori... 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, Complexity : How do the resource needs of a program or algorith... 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, Define the Internal Path Length The In... 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

Develop a material requirements plan, The below figure illustrates the BOM ... 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

Traversing a graph, two standards ways of traversing a graph in data struc... two standards ways of traversing a graph in data structure

Quick sort, This is the most extensively used internal sorting algorithm. I... 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

Algorithm that inputs the codes for all items in stock, A shop sells books,... 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, INSERT FUNCTION /*prototypes of insert & find function... INSERT FUNCTION /*prototypes of insert & find functions */ list * insert_list(list *); list * find(list *, int); /*definition of  anyinsert function */ list * inser

Explain memory allocation strategies, Memory Allocation Strategies If i... 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

Maximum degree of any vertex in a simple graph, The maximum degree of any v... 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.