Shortest paths graph Given a directed graph $G$, edge weights for each edge, source vertex $s$ and $d[v]$ for each vertex in the graph (the distance from $s$ to $v$), I need to find an algorithm that builds the shortest paths graph.

I was thinking of going on edges by BFS, but then how can I know which edge should be in the tree and how to check that the $d[v]$ for each vertex is true?
Thre are multiple algorithms already developed like Dijkstra's algorithm, Bellman-Ford algorithm or A* search algorithm.

The problem you face is also well described on Wikipedia.

Maybe there is something specific about your assignment like memory or time complexity?