2
$\begingroup$

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

$\endgroup$

closed as unclear what you're asking by David Richerby, vonbrand, Juho, Luke Mathieson, Ran G. Oct 28 '15 at 1:06

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

3
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.