Reputation: 157
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
Upvotes: 2
Views: 2284
Reputation: 4601
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).
Upvotes: 1