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
(a) Discuss the role played by Business Intelligence Systems in giving companies strategic advantage. (b) Explain the term heuristics searching . (c) With the use of an appr

Abstract Data Types :- A useful tool for specifying the logical properties of a data type is the abstract data type or ADT. The term "abstract data type" refers to the basic mathem

Complexity classes All decision problems fall in sets of comparable complexity, called as complexity classes. The complexity class P is the set of decision problems which ca

Explain Backtracking The  principal idea is to construct solutions single component  at a time  and evaluate such  partially constructed candidates as follows. If a partiall

Determine the class invariants- Ruby Ruby has many predefined exceptions classes (like ArgumentError) and new ones can be created easily by sub-classing StandardError, so it's

The Linked list is a chain of structures wherein each structure contains data in addition to pointer, which stores the address (link) of the next logical structure in the list.

Explain an efficient way of storing a sparse matrix in memory.   A matrix in which number of zero entries are much higher than the number of non zero entries is called sparse mat

The searching technique that takes O (1) time to find a data is    Hashing is used to find a data

An interesting application or implementation of trees is the playing of games such as tie-tac-toe, chess, nim, kalam, chess, go etc. We can depict the sequence of possible moves

#question.explain different types of errors in data transmission.