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
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 exampleedge and cost each liine... say 2 1 60 means ,,,an edge from 2 to 1 with edge cost 60....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
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:
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 .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 ) );
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 06:08 AM.
Reading your post makes my eyes bleed.
Quzah.
Hope is the first step on the road to disappointment.
So this is your graph. Apparently it is directed, since 1 2 and 2 1 have different values.
We apparently end on node 4. So the priority queue:Code:-<-60-<- / \ 1->-10->-2 |\ | V ^ V | \ | 20 50 5 | \ | V ^ V | \| 3->-10->-4
Now the shortest path from a node is listed in all the steps: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
Look at the graph and convince yourself this is true (assuming I didn't make a mistake)Code:Node Distance 1 15 2 5 3 10 4 0
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
where x denotes infinity1st 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...
and this value doesnt change from then if we procced further...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)
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 03:36 PM.
Hope is the first step on the road to disappointment.
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-11-2009 at 11:53 PM.
In that case, let me fix your original post then (correcting grammar along the way):
There we go, I think that looks about right.Originally Posted by dpp
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
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-11-2009 at 11:56 PM.