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

Define different types of sparse matrix, Q1. Define a sparse matrix. Explai... 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

Explain open addressing, Open addressing The easiest way to resolve a c... 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.

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

Multilist file organisation, what is multilist length file organisation? ex... what is multilist length file organisation? explain with an example

Signals, How does cpu''s part tming and controls generate and controls sign... How does cpu''s part tming and controls generate and controls signls in computer?

Which sorting methods sorting a list which is almost sorted, Which sorting ... 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, Implementation of queue... 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.

Multiple stacks in a single array, implement multiple stacks in an array an... implement multiple stacks in an array and write different algorithms to perform operations on it

Make adjacency matrix for un-directed graph, Q. Describe the adjacency matr... 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, Define Merge Sort  Merge sort is a perfect example ... 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