Блог пользователя I_am_Polish_Girl

Dijkstra Algorithgm
Автор I_am_Polish_Girl, история, 11 месяцев назад, По-английски

Hi codeforces

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

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
11 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +87 Проголосовать: не нравится

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

→ Ответить
»
11 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    11 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

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

      → Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    11 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

    I read your question wrong

    → Ответить
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

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

    → Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Just use bitsets bro

→ Ответить