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

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).

thanks for the reply...

take for example

Quote:

---

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

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 ;).

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

Reading your post makes my eyes bleed.


Quzah.

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)

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

Quote:

---

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)

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.

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

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.

I was just about to post a recipe for peanut-butter apple pie.

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