Блог пользователя bobbilyking

Автор bobbilyking, история, 4 года назад, По-английски

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?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится