Results 1 to 2 of 2

Math Help - LINEAR OPTIMIZATION PROBLEM (Dijkstra's algorithm)

  1. #1
    Junior Member
    Joined
    Dec 2006
    Posts
    48

    LINEAR OPTIMIZATION PROBLEM (Dijkstra's algorithm)

    Dijkstras algorithm does not work for graphs in which some weights are negative. A Natural approach to overcome this problem would be the following:

    To find a shortest path between two vertices in a graph with some negative weights, determine the minimium weight δ<0 among all the edges of the graph. Add some ε >=-δ to every edge making all weights nonnegative. Run Dijstra's algorith and return the shortest path subtracting ε from the weight of every edge of the path.

    Now, Give a counterexample, ie such a graph for which the above approach fails.


    any1 kno of a good counter example they can juss describe to me since we cant draw here unelss sum1 knows how
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Feb 2007
    Posts
    16
    Hello Friend! This is my first "help" post here on math help forum so I'm gonna try my best!


    The biggest problem with negative weights is cycles. I'm not really sure how/if to upload/insert images so I hope my description will be good enough .

    Lets say you have three nodes connected in a graph. If positive weights represent "distance", The negative weights represent a "reward". Given the negative weights, you can get locked into a "reward" cycle where you can just keep moving around in a circle to get reward. Three nodes S, T, and U (no F, har har, little joke) are connected by edges:

    S-T = -1
    T-U = 2
    S-U = 2

    S-T-U is a minimum cost path (-1+2 = 1). How, we'll add a constant (2) to make all the weights positive:

    S-T = 1
    T-U = 4
    S-U = 4

    S-T-U is no longer a minium cost path (1 + 4 = 5 > (S-U) 4). When we return the shortest path (S-U), and subtract our added value (2) we'll get 2, but the answer is obviously bogus since S-U is NOT a shortest path answer in the original graph.


    There's the Bellmen-Ford algorithm for negative weights. It will report a shortest path given negative cost weights, or report the existance of a negative cost cycle. Take a look on google if you interest!


    Have a good day
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Graphs, Dijkstra's algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 11th 2011, 04:20 PM
  2. linear-quadratic regulator optimization problem
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: March 11th 2010, 12:38 PM
  3. Replies: 4
    Last Post: May 10th 2009, 10:29 AM
  4. dijkstra's algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 6th 2008, 12:16 PM
  5. Replies: 0
    Last Post: November 6th 2007, 03:05 PM

Search Tags


/mathhelpforum @mathhelpforum