Results 1 to 3 of 3

Math Help - A* with negative edges

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    2

    A* with negative edges

    I'm researching on shortest path algorithms for a special graph set with negative weights (no neg. cycles)
    I found a consistent A* heuristic for them.

    Now I'm searchign for related work. Unfortunately it seems everybody only works with positive edges. I appreciate if somebody could point be to some literature references. Thx.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    Google search yields Bellman-Ford algorithm and this book chapter. Have you looked in Knuth's "Art of Computer Programming"?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    2
    We know Bellmann-Ford solves the problem in O(n^3).
    Our heuristic for a sub problem solves it in O(n^2).

    We are interested in research about A* for negative edges.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. problem in negative negative exponential distribution
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: July 4th 2011, 08:29 AM
  2. Replies: 2
    Last Post: March 26th 2009, 05:30 PM
  3. Replies: 5
    Last Post: March 26th 2009, 03:36 PM
  4. Replies: 5
    Last Post: June 22nd 2008, 10:20 PM
  5. negative fractions to negative exponents
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 24th 2006, 06:02 PM

Search Tags


/mathhelpforum @mathhelpforum