# Dijkstra’s algorithm

Dijkstra’s algorithm finds shortest paths from a given vertex to all the other in a graph with non-negative edge weights.

Read more on wikipedia.

#### Input

```v e s
a b c (e times)
...```

v – number of vertices
e – number of edges
s – start vertex
a b c – edge between a and b with weight c

#### Sample input

```6 10 1
1 2 2
1 6 1
1 5 3
4 1 5
2 6 2
2 3 5
4 3 4
3 5 4
4 5 4
5 6 3
```

#### Output

The algorithm returns shortest distances from city s to all other cities.

#### Complexity

Implementation of priority queue is important as we need to find the closest vertex (to s) |V| times. Also we need to be able to update item value, but std::priority_queue doesn’t support decrease_key operation.

In my solution as a priority queue I use std::set, which is most often implemented as red-black tree, so all operations are O(logn), therefore decrease_key and push are O(logn). According to this algorithm runs in:

O(|V|·log|V| + |E|·log|V|) = O(log|V| · (|V| + |E|))