[問題] PriorityQueue的同步問題？

[kiwistar (暴風雪之喀秋莎)]

這裡使用的是Java API提供的PriorityQueue.class

java.util.PriorityQueue<E>


我建構一個資料類別MapNode，當中Override了compareTo方法

依照MapNode下面的一個叫做distance的int型態變數作為比較標準

實作Dijkstra's algorithm，始終得到奇怪的結果

作業要求找出1到其他10個點的最小距離(共200個點)

我輸出的結果有大概6個是正確數字，另外4個答案則不對

使用Eclipse 做debug發現，在前面幾個cycle，PriorityQueue都能從我的清單裡面

找出正確的那個，poll出來(我用過remove(), poll()，結果都依樣)

從某一步開始，PriorityQueue給出來的東西不再是距離最小的那一個

應該說，PriorityQueue本身是用heap實作，

所以他應該會把我要的東西放在root，前幾次cycle有看到這個現象

但某次開始突然就不這麼做了

因為前面幾次的結果都正確，我想應該不是override定義的問題

有沒有可能是synchronization還是什麼其他的問題......

5




這問題困擾我很久，結果真的跳進去debug 200個節點的圖，發現是官方的資料結構

沒有正確運作，還滿傻眼的。原先一直以為是我的演算法有邏輯問題......



感謝大家！！


--
推 perry27: 要紅就要有特色 想到盜總就是盜壘 鋒哥就是轟砲 建民就是
→ xyz4594: 持久
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.179.102
※ 文章網址: https://www.ptt.cc/bbs/java/M.1521718479.A.D2A.html
→ kiwistar: 自問自答：根據h3ap
→ kiwistar: 根據heap的原理，要讓他洗牌，需要做insert 或是remove
→ kiwistar: 的操作，所以修改距離後加上一行add(E)就可以了，嗚嗚，
→ kiwistar: 還我數十小時的光陰來