I_am_Polish_Girl's blog

Dijkstra Algorithgm
By I_am_Polish_Girl, history, 10 months ago, In English

Hi codeforces

Do you know how to optimize Dijkstra Algorithm to O(n)? and is it posible?

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
10 months ago, # |
← Rev. 2   Vote: I like it +87 Vote: I do not like it

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

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I know this , and I want to know : can we do this like O(E)

    → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    Fibonacci heaps have a very large constant factor so for the purposes of competitive programming they are rarely faster than priority queues.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      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))$$$

      → Reply
»
10 months ago, # |
  Vote: I like it +15 Vote: I do not like it

I heard that people could solve it in O(n) time if the edge weights are all integers.

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +15 Vote: I do not like it

    I read your question wrong

    → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    It is in fact possible to find the publication for it: https://sci-hub.et-fine.com/10.1145/316542.316548

    → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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).

    → Reply
»
10 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Just use bitsets bro

→ Reply