OJ Board

hello everyone,

I have a problem with multiple shortest path. If there are multiple shortest path exists (form one source not all pair of shortest path) then is it possible to find out multiple shortest path using Disktra or UCS algo? If possible then how. plz explain. if not then with which algo it is polssible.

-shaikat.

This can be done using dijkstra.
When you relax an edge u->v and d[v]== d[u]+ d[u->v] then you add u to a list of 'fathers' of v. When d[v]> d[u]+ d[u->v] then you do the same, but first you clean the list. Now having such lists in all vertices, you can easily build multiple paths between 2 given ones using a dfs. You have to remember though, that the amount of such paths might be exponential

Dear makbet,

thank u for ur reply. Ur reply is very useful to me and i have got the right track. so, aging Thanks to u.

-shaikat.

shaikat wrote:all are cows

dear all visitors,

My account was hacked for 30 minutes today.
I am extreamly sorry for that Quote.
thanks all.

-shaikat.