CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Dec 2012
    Posts
    1

    Shortest Path With Constrains

    I need to solve a graph, but with the a twist:

    My problem is modeled by an edge-based graph (where each edge in the original graph is transformed into a vertex and each edge to edge "turn" is transformed into an edge).

    Each edge in the original graph has multiple grades (in my specific case just two) and I have graded the turns as well. I want to minimize the cost of the solution path over one of the two grades of the edges. In addition, the other grade is a cumulative one and when it reaches a certain threshold it need to reset itself to 0 and this is achieved by taking certain "turns".

    I have been searching for a shortest-path algorithm with constraints, but the problem is that the cumulative grade is based not only on the future vertices in the path, but as well in the past ones.

    Could someone help me with this? A friend told me to try the A* prune algorithm (http://suraj.lums.edu.pk/~te/cspf/A_...Algorithmf.pdf) , but I haven't been able to make it work for me.

    Thanks!
    matigurten

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Shortest Path With Constrains

    I think you need to specify your problem better.

    What's the significance of the transformation of the graph? What's a grade? What's the turns that are taken when a cumultative grade is resetting itself? What's to be solved?

    In short, what exactly does the graph look like when the algorithm is applied and what is it supposed to accomplish?

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured