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

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.

Explain decision tree, Decision Tree A decision tree is a diagram that ... Decision Tree A decision tree is a diagram that shows conditions and actions sequentially and therefore shows which condition is to be considered first, second and so on. It is

Linked list implementation of any circular queue, Link list representation ... Link list representation of a circular queue is more efficient as it employs space more competently, of course with the added cost of storing the pointers. Program 7 gives the link

Doubly linklist, explanation of doubly linklist explanation of doubly linklist

Sorting algorithm, Sorting Algorithm A sorting algorithm is an algorit... Sorting Algorithm A sorting algorithm is an algorithm which puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Eff

Define graph, A graph is a mathematical structure giving of a set of vertex... A graph is a mathematical structure giving of a set of vertexes (v1, v2, v3) and a group of edges (e1, e2, e3). An edge is a set of vertexes. The two vertexes are named the edge en

Array implementation of a queue, Since the stack is list of elements, the q... Since the stack is list of elements, the queue is also a list of elements. The stack & the queue differ just in the position where the elements may be added or deleted. Similar to

Logical database design, 1. For the ER diagram you created in assignment, t... 1. For the ER diagram you created in assignment, the artefact of the conceptual database design, map the ER model into the relational model according to how it was designed in the

Avl trees, An AVL tree is a binary search tree that has the given propertie... An AVL tree is a binary search tree that has the given properties: The sub-tree of each of the node differs in height through at most one. Each sub tree will be an AVL tre

Types of a linked list, A linked list can be of the following types:- ... A linked list can be of the following types:-  Linear linked list or one way list Doubly linked list or two way list. Circular linked list Header linked list