AtCoder Beginner Contest 143 E Travel by Car
https://atcoder.jp/contests/abc143/tasks/abc143_e
Because I hear that O((n + m) log n) Dijkstra is slow, I tried that too. That's indeed slow. I hear that fibonacci heap is faster than binary heap, so I tried that too. That's indeed fast. But does that conclude fibonacci heap is better than binary heap? I doubted that's true. Then, I noticed that this implementation of binary heap doesn't use decrease key. So I tried binary heap with decrease key, then it become faster than fibonacci heap.
| method | time | link |
|---|---|---|
| binary heap without decrease key | 1252 ms | link |
| fibonacci heap | 178 ms | link |
| binary heap with decrease key | 117 ms | link |
To compare performance, I made the following graph: For $j - i \ge 2$, connect i and j with weight $5000(N-i) + \mathrm{rand}(0, 4999)$, and for $j-i=1$, connect i and j with weight 0. In this graph, decrease key will be called N(N-1)/2 times. Moreover, the values in the heap will be shuffled for each iteration. For $N=5000$, the result becomes as follows.
| method | time |
|---|---|
| fibonacci heap | 384 ms |
| binary heap with decrease key | 201 ms |
| binary heap without decrease key | 1539 ms |
| straight forward | 94 ms |
