Dijkstra in the Network
Note: to start work on this task you need to solve Graph Generator to generate input data.
Dijkstra's algorithms solves very popular task - it allows to find the sortest paths from the given node of a graph to all other nodes.
Of course this can find applications in logistics etc., but far more common usage is in communication networks.
For example, think of Zig-Bee network, consisting of
N modules. These small
devices are capable of determining the shortest route to destination extremely fast, notwithstanding that the
network geometry can change over time - some modules can go offline, some other could be installed on vehicles etc.
So most routers in almost every network technology utilize this method or some derivative
In this task you are to implement Dijkstra's algorithm - the details you can find in the corresponding Wikipedia article.
The simplest form (without min-priority queue) would be sufficient.
The graph is described the same way as in Graph Generator problem - by specifying the number of vertices and the seed for randomizer.
For example, if we use the same graph with
10 nodes and initialize random generator with the same seed
0 and will
run the Dijkstra's algorithm starting from node
1, we'll get the following paths to each of destinations:
dest. path length 1 1 0 2 1-2 1 3 1-2-3 2 4 1-2-4 2 5 1-2-4-5 5 6 1-2-4-6 9 7 1-2-4-8-7 4 8 1-2-4-8 3 9 1-2-4-6-9 16 10 1-10 3
The tree of these paths is marked with green lines in the picture above.
Input data will contain three numbers
N - the number of nodes,
X0 - seed for random generator and
index of starting vertex (from where we are to search for paths to others).
Answer should contain the route length to each vertex in the graph.
input data: 10 0 1 answer: 0 1 2 2 5 9 4 3 16 3
Attention: the length of the answer will be several kilobytes long - not very much, so it would give you no problem when copying and pasting it - but take care not to truncate it accidentally.