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

Write an algorithm outputs number of books using psuedocode, A shop sells b...

A shop sells books, maps and magazines. Every item is identified by a unique 4 - digit code. All books have a code starting with a 1, all maps have a code which starts with a 2 and

Data searching, In file access: what is the difference between serial, seq...

In file access: what is the difference between serial, sequential and indexed sequential searching

Estimate best first search nodes , Given the following search tree, state t...

Given the following search tree, state the order in which the nodes will be searched for breadth first, depth first, hill climbing and best first search, until a solution is reache

C++ function, Write c++ function to traverse the threaded binary tree in in...

Write c++ function to traverse the threaded binary tree in inorder traversal

Advanced trees, Linked list representations contain great advantages of fle...

Linked list representations contain great advantages of flexibility on the contiguous representation of data structures. However, they contain few disadvantages also. Data structur

Implement the physat algorithm, The first assignment in this course require...

The first assignment in this course required you to acquire data to enable you to implement the PHYSAT algorithm (Alvain et al. 2005, Alvain et al. 2008) in this second assignment

Define container in terms of object-oriented terms, Define container in te...

Define container in terms of  object-oriented terms A Container is a broad category whose instances are all more specific things; there is never anything which is just a Contai

The number of different directed trees with 3 nodes, The number of differen...

The number of different directed trees with 3 nodes are ?? The number of disimilar directed trees with three nodes are 3

Algorithm to insert element to a max-heap sequentially, Q. Write  down the ...

Q. Write  down the  algorithm  to  insert  an  element  to  a  max-heap  which  is  represented sequentially.           Ans: The algorithm to insert an element "newkey" to

Stack and queue, write a algorithsm in c to perform push and pop operation...

write a algorithsm in c to perform push and pop operations stastic implementation using array ?

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