Graphs with negative edge costs, Data Structure & Algorithms

Assignment Help:

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).


Related Discussions:- Graphs with negative edge costs

Life science, Define neotaxonomy. Discuss how electron microscopy can help ...

Define neotaxonomy. Discuss how electron microscopy can help in solving a zoological problem faced by taxonomist.

What is an algorithm, What is an algorithm?  What are the characteristics o...

What is an algorithm?  What are the characteristics of a good algorithm? An algorithm is "a step-by-step process for accomplishing some task'' An algorithm can be given in many

State the example of pre- and post-conditions, State the example of pre- an...

State the example of pre- and post-conditions Suppose that function f(x) should have a non-zero argument and return a positive value. We can document these pre- and post-condit

Algorithm of decorated graph, As we talked in class, a program with two int...

As we talked in class, a program with two integer variables is universal. Now, we consider a special form of four variableprograms. Let G = (V; E) be a directed graph, where V is a

Threaded Binary Tree, If a node in a binary tree is not containing left or ...

If a node in a binary tree is not containing left or right child or it is a leaf node then that absence of child node can be represented by the null pointers. The space engaged by

Stack, using a program flowchart design a program to illustrate pop and pus...

using a program flowchart design a program to illustrate pop and push operation

Hash tables, Q. Explain the Hash Tables, Hash function and Hashing Techniqu...

Q. Explain the Hash Tables, Hash function and Hashing Techniques properly?             A n s . H as h Table is explained as follows : A hash table is a data struc

Pipelining., How branching takes place in Instruction pipeline. Explain wit...

How branching takes place in Instruction pipeline. Explain with suitable examples

Adjacency matrix, Q. Give the adjacency matrix for the graph drawn below:  ...

Q. Give the adjacency matrix for the graph drawn below:                                                 Ans: Adjacency matrix for the graph given to us

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd