Armyx's blog

TreeSet much faster than PriorityQueue — Dijkstra
By Armyx, history, 9 years ago, In English

I solved this problem http://mirror.codeforces.com/contest/449/problem/B using dijkstra based on priority queue and I got TLE (http://mirror.codeforces.com/contest/449/submission/13186398) on test 45. After that I changed it to TreeSet ( http://mirror.codeforces.com/contest/449/submission/13186483 ) and it runs ~940ms instead of > 2000ms . What is wrong with my previous solution ? I read that priority queue runs faster in practice and I saw that most java solutions use priority queue

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Priority queue doesn't work in Dijkstra when you store only indices in it, try to think why.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Priority queue doesn't work in Dijkstra when you store only indices in it

    it does: 13187441

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      When the distance to some vertex is changed, this vertex doesn't change its position in the priority queue, while it should to maintain the heap property value(parent) <= value(child). So it's just weak tests.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        CountZero has defined a custom comparison for the PriorityQueue and ignores vertices already visited so it is fundamentally correct.

        EDIT: Have a look at the analysis

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          lol, no. Now I see dalex is right. Take a closer look at my code — there are no guarantees for heap property to be maintained. Anyway, we can implement Dijkstra algorithm using priority queue and custom comparator — we need a custom priority queue with method "delete any element".

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            Understood my mistake. Please ignore.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Of course it's correct, they store pairs (vertex, distance).

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Thanks, I understand now.

                → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            BTW, you don't need 'delete any element' in priority-queue.

            You can store a pair <vertex,distance(vertex)> in the priority-queue.

            → Reply