Hi codeforces
Do you know how to optimize Dijkstra Algorithm to O(n)? and is it posible?
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 160 |
5 | djm03178 | 158 |
5 | -is-this-fft- | 158 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
9 | awoo | 152 |
10 | luogu_official | 150 |
Hi codeforces
Do you know how to optimize Dijkstra Algorithm to O(n)? and is it posible?
Name |
---|
its pretty easy. proof:
let v = # of vertices.
let e = # of edges.
then, let n = V + ElogV. this gets us a O(n) time complexity. q.e.d
Not bad, but TL say "it is nlog"
We can optimize it using data structures in $$$\mathcal{O}((V + E)\log V)$$$
as an example we can use a Fibonacci Heap as follows:-
Replace the binary heap with a Fibonacci Heap for the priority queue. Fibonacci Heaps can decrease the time complexity of Dijkstra's algorithm to $$$\mathcal{O}((V + E)\log V)$$$. They have better amortized time complexity for decrease-key operations, which are common in Dijkstra's algorithm.
UPD: as I know : No We Can't Optimize, even it's kind of wired thing to only use $$$E$$$ and ignore $$$V$$$ and vice versa.
I know this , and I want to know : can we do this like O(E)
Fibonacci heaps have a very large constant factor so for the purposes of competitive programming they are rarely faster than priority queues.
You're right sometimes it'll give very large constant factor , so alternative optimization is merging Buckets
In practice, you can achieve efficient results by combining Dijkstra's algorithm with a bucket-based data structure. Divide the vertices into buckets based on their distance from the source. Process vertices in a bucket in non-decreasing order of distance. This reduces the number of vertices to consider in each iteration.
which will reduce the storage , still The complexity $$$\mathcal{O}((V+E)\log(V))$$$
I heard that people could solve it in O(n) time if the edge weights are all integers.
I read your question wrong
It is in fact possible to find the publication for it: https://sci-hub.et-fine.com/10.1145/316542.316548
There is a theoretical linear-time algorithm for undirected SSSP with integer weights, yes: Thorup, 1999.
As you might expect, though, it's very complicated to implement in practice, still slower than the usual Dijkstra in typical cases, and the current word size we have in modern computers is still too small to make the algorithm perfectly linear (current implementations make some compensations to this and modified the algorithm in several places).
Just use bitsets bro