Dijkstra's algorithm - Finding additional paths with same weight but different edges given a network with n stations. assuming the shortest between s,t was found using dijkstra's algorithm. let that path be denoted as $(a_1,a_2,...,a_k)$

assume that between the nodes s and t, there's an at least additional path with the same weight, but with different edges(meaning both paths have different edges, nothing in common). how can we find that additional path?

My attempt: let's create an array that holds the parent. that array will be separate, so the value of $parent[v_i]$ for some vertex $v_i \in V$ stores the parent of $v_i$ in the array, in the shortest path tree that is formed by the algorithm. now, we'll initiate the first element, meaning the parent of the root to be -1, and if we find shorter path through some vertex u, we can make u the parent of the current vertex. but i am not sure it solves the problem unfortunately.

would really appreciate if you could explain what you do so i can understand it.

tried to do a research on the site, but couldn't find a similar problem with no same edges and i don't know how to solve it, so i am asking for help here

thank you very much
One way to proceed may be to store for each node a list of parents so $parents[v_i]$ becomes an array of lists. There is also the same array of distance from $s$, $d[v_i]$ initially infinite for all $v_i$ but $s$ ($d[s] = 0$).

So like standard version of Dijkstra's algorithm, you maintaint a priority queue $q$ (sorted by $d$). When $v_i$ is depiled from the queue you explored all the nodes $v_j$ reached from $v_i$, in the standard version of the algorithm, there was 2 cases:


a smallest path to $v_j$ has been found: $d[v_j]$ and $parents[v_j]$ are updated and $v_j$ is added to the queue.
the new path is not better, do nothing.


So now, if the path is smallest, $parents[v_j]$ is replaced by the list with one element $[v_i]$.

And there is an additional case: if path to $v_j$ is exactly the same in distance, append $v_i$ to $parents[v_j]$. Note that there is no need to put $v_j$ again in the queue.

Once you reach $t$ and you backtrack path using $parents[v_i]$, if there are several elements in the list, any may be picked and lead to a different shortest path.

Note that $parents[v_i]$ is $O(N^2)$ in space. The worst cases are very dense graphs,  and this would mean that there is a large number of shortest paths. In this case, other method to store $parents[v_i]$ may be more adapted.