Problem Detail: How to find all shortest paths between node 1 and N in a weighted undirected graph? There can be multiple edges between two nodes. I want to find all nodes that can be on a shortest path. For example:
10 11 1 2 1 1 3 1 3 4 2 4 5 1 5 6 1 5 10 2 1 7 1 7 8 3 7 9 2 9 10 2 8 10 1
The answer is
1 7 8 9 10
because there are two shortest ways
1 7 8 10
and
1 7 9 10
Asked By : user4201961
Answered By : D.W.
To tell whether a vertex $v$ is along some possible shortest path from $s$ to $t$, compute $d(s,v)$ (the length of the shortest path from $s$ to $v$) and $d(v,t)$, and then….. You can compute $d(s,v)$ for all vertices $v$ efficiently using…. (It’s your exercise, so I’ll let you have the pleasure of working out how to fill in the blanks.)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/48656 3.2K people like this
