# How to find all shortest paths between two nodes in a weighted undirected graph? [closed]

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

1 7 8 9 10

because there are two shortest ways

1 7 8 10

and

1 7 9 10

• What do all those lists of numbers mean? Oct 24, 2015 at 9:00
• Possible duplicate of Is there an algorithm to find all the shortest paths between two nodes? Oct 24, 2015 at 9:01
• First two numbers are how many vertices and edges are in a graph. Other numbers are descriptions of edges A, B, C, means A - B weigh C. Oct 24, 2015 at 9:05

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