Dijkstra's with priority queue w/o all the clutter? (Java)

Revision en1, by bobbilyking, 2020-06-08 19:11:36

So my implementation of dijkstra's doesn't actually sort the nodes, instead it keeps on duplicating nodes, updating shorter distances. This works, because if there are 2 duplicate nodes and one distance is shorter, it would only check the shorter node and the longer distance node remains forever unseen. However, since you're constantly duplicating nodes, doesn't this take up a bunch of unnecessary memory?

Is that that just pqueue things or is there a better way to deal with this?

Tags dijkstra, java memory usage

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English bobbilyking 2020-06-08 19:11:36 546 Initial revision (published)