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

Infix expression into the postfix expression, Q. Convert the given infix ex...

Q. Convert the given infix expression into the postfix expression (also Show the steps) A ∗ (B + D)/ E - F(G + H / k ) Ans. Steps showing Infix to Post fix

Stack, write pseudocode to implement a queue with two stacks

write pseudocode to implement a queue with two stacks

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.

Multidimensional array in one dimensional array, Q. By giving an example sh...

Q. By giving an example show how multidimensional array can be represented in one the dimensional array.

COBOL, write a COBOL program to find the biggest of two numbers

write a COBOL program to find the biggest of two numbers

Tree traversal, Q. What do you understand by the tree traversal? Write down...

Q. What do you understand by the tree traversal? Write down the procedure for traversing a binary tree in preorder and execute it on the following tree.    Ans: Th

Four applications or implementation of the stack, Q. Write down any four ap...

Q. Write down any four applications or implementation of the stack.                                     Ans. (i)       The Conversion of infix to postfix form (ii)

Explain about franklin algorithm, Explain about Franklin Algorithm We m...

Explain about Franklin Algorithm We mentioned how the number of possible comparisons of polygons grows as the square of the number of polygons in the scene. Many of the hidden-

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

Define techniques of dry running of flowcharts, Explain the term- Dry runni...

Explain the term- Dry running of flowcharts  Dry running of flowcharts is essentially a technique to: Determine output for a known set of data to check it carries out th

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