# Dijkstra in the Network

Problem #84

Tags: graphs popular-algorithm data-structures

Who solved this?

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 (like A*).

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 `S` the 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.

Example:

``````input data:
10 0 1