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

Printable View

- 05-10-2009dppSingle 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 - 05-10-2009EVOEx
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). - 05-10-2009dpp
thanks for the reply...

take for exampleQuote:

1 2 10

2 1 60

1 3 20

3 4 10

2 4 5

4 1 50

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 - 05-10-2009EVOEx
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 ) );

- 05-10-2009dpp
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 - 05-11-2009quzah
Reading your post makes my eyes bleed.

Quzah. - 05-11-2009EVOEx
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

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

Code:`Node Distance`

1 15

2 5

3 10

4 0

- 05-11-2009dpp
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

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

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) - 05-11-2009quzah
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. - 05-11-2009dpp
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 - 05-11-2009arpsmack
In that case, let me fix your original post then (correcting grammar along the way):

Quote:

Originally Posted by**dpp**

- 05-11-2009neandrake
I was just about to post a recipe for peanut-butter apple pie.

- 05-11-2009dpp
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