As has been pointed out, there are well known shortest path algorithms. But your problem already has most of the information. Specifically, you already know the shortest path distances $d[v]$ from $s$ for each node $v$. In such a case, you can use a much better algorithm.
By a "shortest paths graph", I think you mean a collection of shortest paths from $s$ to every other vertex $v$. In such a case, you can use a Depth First Search (DFS) as follows:
- Start the DFS from the source vertex $s$.
- Mark a node visited as soon as you reach it for the first time.
- For every node $u$ visited, do a DFS on all children $v$ of $u$ only if $d[v] = d[u] + w(u, v)$, where $w(u, v)$ is the weight of the edge from $u$ to $v$.
- If a child $v$ of $u$, which obeys the previous condition of distances, has already been visited, it simply means that there are multiple shortest paths from $s$ to $v$, and that you have already selected some other such path which does not go through $u$. In such a case, do not include this edge $(u, v)$ in your shortest paths tree/graph. This is because by doing a DFS, you have already selected all shortest paths that go through $v$.
Note that this algorithm relies on the following property of a shortest path algorithm: edge $(u, v)$ is on some shortest path to $v$ from $s$ if and only if
$d[v] = d[u] + w(u, v)$. Therefore, only the shortest paths are taken by the algorithm. Since we ignore a shortest path from $s$ to $v$ through $u$ if and only if $v$ has already been visited, we ensure that all shortest paths are included.
Note that this algorithm is linear in the size of the graph. I mention DFS, since it is much easier to program for such a scenario, and recursion holds the stack implicitly.
However, you can use BFS too for this purpose. Use the same property in the BFS as above, that is:
- Enqueue (and mark visited) only those neighbors $v$ of $u$ which obey the following property: $d[v] = d[u] + w(e, v)$.
Note that if there are multiple shortest paths to some vertex $v$ from $s$, using a DFS or a BFS may give different shortest path trees (though both will be correct). DFS will give a random tree, whereas BFS will give a tree where the shortest path selected would be such that it will also have the minimum number of edges among all shortest paths from $s$ to $v$. Unless you desire such a property, I think a DFS would be much simpler.
See this Udacity nugget for more information about how to compare these algorithms and a more in depth explanation.