Thread: 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

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 .

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

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)

In that case, let me fix your original post then (correcting grammar along the way):

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.