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

  • 1
    $\begingroup$ Please use extra care with the spelling of a person's name. While mildly annoying for famous ones like Dijkstra's, it becomes a nuisance, e.g, trying to find publications from non-prominent authors $\endgroup$ – greybeard Jan 24 '20 at 6:15
  • $\begingroup$ What have you tried? Rather than looking for someone else who has solved this exact problem, I suggest you spend some time thinking about how you might solve this problem. Try working through some small examples by hand, and see what process you're using. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Jan 24 '20 at 6:18
  • $\begingroup$ (Please use proper capitalisation, e.g., with I and at the beginning of sentences. Time allowing, (re)visit How do I ask a Good Question?) $\endgroup$ – greybeard Jan 24 '20 at 6:24
  • $\begingroup$ If you're not sure whether your approach works, your next step should be to figure that out. Try it on many small examples to see if works correctly on them. Try to prove it correct. $\endgroup$ – D.W. Jan 24 '20 at 6:26
  • $\begingroup$ stuck with it for long hours/days and i am not sure how to continue. i tried my attempt on several sets, but it seems not to solve the problem. reason i asked here is because i tried it several times and i stuck, so i am asking for an answer so i can learn how to do it correctly $\endgroup$ – Networker Jan 24 '20 at 6:29

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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