bobbilyking's blog

By bobbilyking, history, 16 months ago, In English

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?

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