Darknesscrysis

Question MinPrioQueue of record pascal

Apr 25th, 2020
897
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Min priority queue for record in pascal
  2.  
  3. I have some records like this
  4.  
  5. TNode = record
  6.   name: String;
  7.   edges: TNodeArray;
  8. end;
  9. TNodeArray = Array of TNode;
  10.  
  11. I want to have a priority queue to use dijkstra's algorithm with this type of record. There is a step in the algorithm that is like this. 'For each neighbor of the current node that isn't visited, check the distance to it through the current node and if it's less than the current distance update it'. To update that distance (priority) efficiently I need to access the queue by index so I have to do something like:
  12.  
  13. for v in edges
  14.  if dist < currentDist
  15.    DecreaseKey(v, dist);
  16.  
  17. Then DecreaseKey has to look at v.idx to know which node from the queue to look for. So the record would need an additional variable idx.
  18.  
  19. I would like to have the queue with an example Main showing how the queue works with a few records. I've done a MinPriorityQueue with a Main that works but not for the algorithm. I would like one that I can use. I've tried to do it but haven't been able to test it so I'll let it here in case it helps with the answer. MinPriorityQueue, Main.
  20.  
  21. There is one thing I don't like about my implementation. I've used an array where I don't occupy the first position so the childs of a node where in position 2*i and 2*i + 1. But I have to be translating indexes when I use the queue. It would be better if the implementation uses the whole array or translates by itself the indexes given to it.
RAW Paste Data