2

Is it possible that Dijkstra's Algorithm can be used to calculate N shortest paths from single source to a single destination, where N is the number of nodes? I understand that Dijkstra outputs the shortest path from a single source to all nodes in the graph but while I was reading a research paper, the author mentioned the use of Dijkstra to calculate N shortest paths between s and t and that what confuses me a bit.

The following is a quote from the original paper: Capitalizing on SDN-Based SCADA Systems: An Anti-Eavesdropping Case-Study Found also here

Dijkstra’s algorithm [22] is used to calculate the N shortest routes (step 5), in N stages. Considering N = 2, in the first stage, Dijkstra’s algorithm identifies the shortest route between the two network devices, and subsequently all link costs have their weight increased by a tenfold factor. Immediately after, in the second stage (and with the link costs increased), Dijkstra’s algorithm is executed again to return the second shortest route. Finally, also in the second stage, the link costs of the first route are reestablished to the original values. As explained later, the N shortest routes will be used to deliver a communication flow using different paths and, for this reason, they are stored to be used afterwards

Improve this question
3
  • 1
    Dijkstra published several algorithms. Even the one generally referred to as "Dijkstra's algorithm" has several variants. You can generally infer which one from context. Can you cite the paper in question, or quote it? Commented Nov 25, 2015 at 2:12
  • Do you mean find shortest path between s and t that cover exactly N paths? Commented Nov 25, 2015 at 2:13
  • Thank you. I've quoted the paragraph that mentions this idea. Commented Nov 25, 2015 at 2:24

1 Answer 1

Reset to default
1

The N here appears to be a parameter the authors control, not specific to the graph traversal algorithm. They use the algorithm to find the shortest path between a source and target station.

Next, the algorithm calculates the N shortest routes between the master station and the specific substation, ...

N is the number of stages. They do it once, find the shortest path, and bump the cost on the links (multiply it by 10). Then they run the algorithm again on the new updated link costs to find the second shortest (least cost) path, and so on, N times.

Then at the very end they reset the link costs to their original values.

They are not describing some fancy N-pairs shortest paths, but merely an application of the same classic shortest-path-between-s-and-t algorithm N times (with different link costs at each run).

other variants

Quoting wikipedia on this:

The algorithm exists in many variants; Dijkstra's original variant found the shortest path between two nodes,[2] but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest path tree.

You could use one run of Dijkstra's to compute from one selected source node the shortest path to all other nodes, but in the paper's case here, it's always between the same source (master station), and destination (substation).

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thank you very much for your explanation. So simply the algorithm is run as is for N times such that each time the cost of links is multiplied by 10. I just don't see how increasing the cost of links each iteration would change the shortest path!
In order for the same path to be selected again as the shortest on a subsequent iteration, it would need to be still the shortest after its length was multiplied by 10. I haven't read the full paper, but presumably you would use the "second shortest" route as your next candidate if you found your favorite shortest path to be down/congested.
you stated They are not describing some fancy N-pairs shortest paths, but merely an application of the same classic shortest-path-between-s-and-t algorithm N times (with different link costs at each run) can you provide me a source that explain one of these fancy ones? THANK YOU

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.