Data Structure

• struct intList
  value
  next

  : integer
  : self referential pointer
• struct Vertex
  ID
  xAxis
  yAxis
  adjList
  predecessor
  distance

  : integer
  : integer
  : integer
  : pointer to struct intList
  : integer
  : float
• struct vertex array
  • Size same as number of nodes
  • Location of elements tracked by integer array below
• integer array
  • Size same as number of nodes
  • i'th location of array tracks element with ID equal to i

The Algorithm

The data file is read and the vertex array is populated with necessary values. Both predecessor and distance are reset to a value of -1 where for predecessors it represents "no predecessor" and for distance, it represents "infinity".

After this queries are read. For each query, the starting element is moved to the top of the vertex array and integer array is updated accordingly. The vertex array is divided into 2 parts, the min-heap at the upper portion and the completed list at the lower portion of the vertex array.

Until destination array is removed from the min-heap or the min-heap is completed, the top-most element of the min-heap (let us call it ELEM) is swapped with the last element in min-heap and ELEM is then considered part of the completed list (integer array is updated for all changes in vertex array).

The vertex ELEM was swapped with is downward heapified. The vertices in the adjacency list of ELEM are then considered as long as they are not present in the completed list. If the new distance form ELEM is lesser than what already is, then the distance and predecessor of this element is updated and upward heapified. The process is updated until termination of loop. Using predecessor information, the path traversed is computed.