md5
May 14th, 2009, 09:53 AM
hi..
I am pretty familiar with dijkstra's dealing single source shortest path...
Regarding Single destination shortest path my search results say that it is the same as single source shortest path with edges reversed... well i am not able to get it clearly how it is.... and why it is....
can someone explain me how it works by reversing edges and following t dijkstra's single source algo....
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(considering 4 the destination as the source) will have priority queue values like...
1st iteration:
vertex : 4 3 2 1
d value: 0 x x 50 where x denotes infinity
2nd:
vertex : 4 3 2 1
d value: 0 7 60 50
and remains the same value if we proceed further...
now the shpath from 4 to 1 is 50...(obvious from the priority queue values)
but how can i detect the shpath from 3 to 1and 2 to 1 etc from the above approach....
I am pretty familiar with dijkstra's dealing single source shortest path...
Regarding Single destination shortest path my search results say that it is the same as single source shortest path with edges reversed... well i am not able to get it clearly how it is.... and why it is....
can someone explain me how it works by reversing edges and following t dijkstra's single source algo....
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(considering 4 the destination as the source) will have priority queue values like...
1st iteration:
vertex : 4 3 2 1
d value: 0 x x 50 where x denotes infinity
2nd:
vertex : 4 3 2 1
d value: 0 7 60 50
and remains the same value if we proceed further...
now the shpath from 4 to 1 is 50...(obvious from the priority queue values)
but how can i detect the shpath from 3 to 1and 2 to 1 etc from the above approach....