Priority Queue-val jóval jobb, mint n^2. Pár éve írtam ilyet egy courseras tanfolyamon, még megvan a kód, én kipróbálnám ezen a 8200 csúcsú gráfon, bár nem az R-ben van, hanem C++-ban.