Single destination shortest path

This is a discussion on Single destination shortest path within the Game Programming forums, part of the General Programming Boards category; hi..i ve been familiar with single source shortest path...dijkstra's... wat if i want to solve single destination shortest path.... can ...

  1. #1
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197

    Single destination shortest path

    hi..i ve been familiar with single source shortest path...dijkstra's...

    wat if i want to solve single destination shortest path....

    can i modify the approach of single source dijkstra's to find this.... plz let me know...
    thanks

  2. #2
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Do it exactly like dijkstra, only starting from the end and moving towards the other nodes. And in stead of testing whether you're at some node, just store it as the shortest path from that node. If you catch my drift.
    It's pretty much dijkstra, just reading the graph in the other direction (if it is directionaly).

  3. #3
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    thanks for the reply...

    take for example
    1 2 10
    2 1 60
    1 3 20
    3 4 10
    2 4 5
    4 1 50
    edge and cost each liine... say 2 1 60 means ,,,an edge from 2 to 1 with edge cost 60....



    like wise by applying dijstra's from 4(the destination vertex) will have "D"values like...

    1st iteration:

    vertex : 4 3 2 1
    d value: 0 x x 50

    2nd:

    vertex : 4 3 2 1
    d value: 0 70 60 50
    and statys the same value if we proceed further...



    now the shpath from 4 to 1 is 50...
    but how can i detect the shpath from 3 to 1,2 to 1 ,from the above approach....

    thinks i am clear

    waiting fro the reply

  4. #4
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    I didn't read your post as it requires me to think too much. I will describe the best algorithm to use here, in pseudo code. Note that this will only work if the graph has no negative weights:
    Code:
    P = priority queue with pair values ( node, total_distance). On a pop, the node with the lowest total_distance comes out. So NOT based on the node or the highest total distance.
    Done = array of max_node booleans set to false
    P.push(Begin Node, 0)
    while P is not empty
      current_node = P.front().current_node;
      current_distance = P.front().total_distance;
      P.pop();
    
      // Make sure we do the node only once. We always get the shortest distance
      if done[current_node]
        continue;
      done[current_node] = true;
    
      foreach V in vertexes to current_node
        P.push( ( V.begin_node, V.distance + current_distance ) );
    I'm not going to proof it, but this is a fairly basic, dijkstra based, breadth first search. If you have any questions, please ask them and I will attempt to understand your problem at least .

  5. #5
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    thanks for the reply EVOEx....
    well i ve implemented a similar one.....
    infact dijkstar's is the same evrywhr


    wat i posted in last post ,was how the priority queue would look like... at each stage....(with "d "as the key value.....

    hope u understood from my post...........

    from that, it is very evident to determine shortest distance from 4 to 1....
    but from the priority queue values how do i determine shortest distance from 3 to 1 ,,,2 to 1 .... etc....

    because the approach is for single sorce ,if i keep 4 as the source and start from it .....i cud find shpath from 4 to all the vertices...but i am not able to satisy my requirement.....

    could u plz help me out with this
    Last edited by dpp; 05-11-2009 at 07:08 AM.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Reading your post makes my eyes bleed.


    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    So this is your graph. Apparently it is directed, since 1 2 and 2 1 have different values.

    Code:
     -<-60-<-
    /        \
    1->-10->-2
    |\       |
    V ^      V
    |  \     |
    20  50   5
    |     \  |
    V      ^ V
    |       \|
    3->-10->-4
    We apparently end on node 4. So the priority queue:
    Code:
    - Push the end node with distance 0: (4, 0)
    P: ( 4, 0 )
    - Get the nodes we can travel from to here, and push them with the added weights: ( 2, 5), (3, 10)
    P: ( 2, 5 ), ( 3, 10 )
    - Repeat the same step for node ( 2, 5 ): ( 1, 5 + 10 )
    P: ( 3, 10 ), ( 1, 15 )
    - Repeat the same step for ( 3, 10 ): ( 1, 10 + 20 )
    P: ( 1, 15 ), ( 1, 30 )
    - Repeat the same step for ( 1, 15 ): ( 2, 15 + 60 ), ( 4, 15 + 50 )
    P: ( 1, 30 ), ( 4, 65 ), ( 2, 75 )
    - We already visited 1, so ignore
    P: ( 4, 65 ), ( 2, 75 )
    - We already visited 4, so ignore
    P: ( 2, 75 )
    - We already visited 2, so ignore
    P:
    - Empty, so we're done
    Now the shortest path from a node is listed in all the steps:
    Code:
    Node  Distance
    1     15
    2     5
    3     10
    4     0
    Look at the graph and convince yourself this is true (assuming I didn't make a mistake)

  8. #8
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    thanks EVOex for ur reply....
    If we start from node 4 its adjacent list will be just 1

    the priority queue at each step will be

    1st iteration:

    vertex : 4 3 2 1
    d value: 0 x x 50
    where x denotes infinity


    Code:
    since initially 4 is the source....
    scanning its adjacent list then : adj(4)=1 with cost 50 ...so push 50 in queue...

    Code:
    2nd:
    
    vertex : 4  3    2   1
    d value: 0 70  60  50 
    since 1 is extracted and then search adj(1)={3 with cost 70 and 2 with cost 60} so add to queue...
    and this value doesnt change from then if we procced further...
    hope u get me...



    now the shpath from 4 to 1 is 50...

    wat is the shpath from 3 to 1???(ie.how do i determine from the Queue value)

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    If you are storing the weights of moving to any adjacent node on the node itself, then you simply move from one node to every neighboring node (flood fill/BFS) until you find the node you want to end up with, adding up all the paths as you go.

    3 -> 1 = 60. 3 -> 4 (10) + 4 -> 1 (50)

    [edit] All it is is a simple BFS, but instead of incrementing the path depth / total count by 1 per move, you're incrementing by whatever the "cost" of moving a direction is. Instead of having the shortest path of actual moves, you have the "shortest" by weighted number. So while it may be only 1 square away to get somewhere, it may actually be more expensive than if you moved two or three squares that happen to be weighted less.[/edit]

    Quzah.
    Last edited by quzah; 05-11-2009 at 04:36 PM.
    Hope is the first step on the road to disappointment.

  10. #10
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    can i not do it exactly in dijkstra's(single source approach by reversing edges).....

    (i mean ...i found out that single destination shpath is nothing but single source shpath with edges reversed....but i dont understand wat it means)
    and how it is....

    i want to make that one clear
    Last edited by dpp; 05-12-2009 at 12:53 AM.

  11. #11
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    In that case, let me fix your original post then (correcting grammar along the way):
    Quote Originally Posted by dpp
    Hi. I have absolutely no idea what I'm doing. I especially know nothing about Dijkstra's algorithm, but I need to solve the Single Destination Shortest Path problem.

    Keep in mind, even if you explain it to me in detail - possibly even going above and beyond and posting code or pseudo code - I will have no idea what you are talking about and won't be any closer to finding a solution.

    P.S. - I still want you to answer my questions and take time out of your day to post code because I hate you.
    There we go, I think that looks about right.

  12. #12
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    I was just about to post a recipe for peanut-butter apple pie.
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  13. #13
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    correction...i very well know dijkstra's dealing single source shpath...i know its all about bfs and min-heap..
    i am not asking about that for ur kind information....and if i dont know i wouldnt ve explained the test case with priority queue values at each step....

    I just browsed and found out that single src and dest : are just same except with edges reversed...

    i need to clarify with only that.... i just need that answer....... not anything else....
    u dont seem to understand my qstn
    Last edited by dpp; 05-12-2009 at 12:56 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. shortest path single destination
    By steaky1212 in forum Game Programming
    Replies: 6
    Last Post: 07-07-2009, 10:42 AM
  2. Shortest Path Maze Solver (Breadth Search Help)
    By Raskalnikov in forum C Programming
    Replies: 5
    Last Post: 04-07-2009, 08:41 PM
  3. shortest path algorithm prob
    By Marrah_janine in forum C Programming
    Replies: 2
    Last Post: 10-14-2007, 10:06 PM
  4. Shortest path problem
    By Digitalxero in forum C++ Programming
    Replies: 0
    Last Post: 10-25-2005, 06:32 PM
  5. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21