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

Basic organization of computer system, what happen''s in my computer when ...

what happen''s in my computer when i input any passage

Multiple queue, #questionalgorithm for implementing multiple\e queues in a ...

#questionalgorithm for implementing multiple\e queues in a single dimensional array

Algorithms & flowchart, write an algorithm to find the average number of oc...

write an algorithm to find the average number of occurances of MECHANIL in an english passage

General Tree, How to create an General Tree and how to search general tree?...

How to create an General Tree and how to search general tree?

Branch and Bound method, give some examples of least cost branch and bound ...

give some examples of least cost branch and bound method..

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

Write a function that performs integer division, Write a function that perf...

Write a function that performs integer division. The function should take the large number in memory location 1 and divide it by the large number in memory location 2 disregarding

Matrices multiplication, Write an algorithm for multiplication of two spars...

Write an algorithm for multiplication of two sparse matrices using Linked Lists.

Operation of algorithm, Operation of Algorithm The following sequence o...

Operation of Algorithm The following sequence of diagrams shows the operation of Dijkstra's Algorithm. The bold vertices show the vertex to which shortest path has been find ou

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