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 the term heuristics searching, (a) Discuss the role played by Busin... (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, Abstract Data Types :- A useful tool for specifying th... 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, Complexity classes All decision problems fall in se... 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, Explain Backtracking The  principal idea is to co... 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, Determine the class invariants- Ruby ... 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

Linked lists - implementation, The Linked list is a chain of structures whe... 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.

Efficient way of storing a sparse matrix in memory, Explain an efficient wa... 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, The searching... The searching technique that takes O (1) time to find a data is    Hashing is used to find a data

The game tree, An interesting application or implementation of trees is the... 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

Data communication, #question.explain different types of errors in data tra... #question.explain different types of errors in data transmission.