Min P Q Algorithm
The Min P Q Algorithm, also known as the Dijkstra's algorithm, is a widely-used graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights, producing a shortest path tree. This algorithm was conceived by computer scientist Edsger W. Dijkstra in 1956 and published in 1959. The algorithm exists in many forms but is most often used to calculate the shortest path between a starting node and all other nodes in the graph. It works by iteratively selecting the vertex with the lowest distance estimate, updating the distance estimate for its neighbors, and marking the vertex as visited, until all vertices have been visited or the shortest path to the target node has been found.
In operation, the Min P Q Algorithm maintains a priority queue (often implemented as a min-heap) of vertices ordered by their distance estimates. Initially, the distance estimate for the starting node is set to 0, and all other distances are set to infinity. The algorithm then repeatedly extracts the node with the smallest distance estimate from the priority queue, updates the distance estimates for its neighbors, and inserts the updated neighbors back into the priority queue. This process continues until the priority queue is empty, or the target node has been visited. Once the algorithm terminates, the shortest path can be reconstructed by following the predecessor pointers from the target node back to the starting node. The Min P Q Algorithm has a time complexity of O(|V|^2) for dense graphs when using an adjacency matrix and O(|V|+|E|log|V|) when using an adjacency list and a binary heap.
package org.gs.queue
import scala.collection.mutable.ArrayBuffer
/** For min value on Q extends PriorityQueue
*
* @tparam A keys are generic and ordered using [[PriorityQueue.greater]]
* @param pq priority queue array
* @param ord implicit Ordering
* @see [[https://algs4.cs.princeton.edu/24pq/MinPQ.java.html]]
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
class MinPQ[A](pq: ArrayBuffer[A])(implicit ord: Ordering[A]) extends PriorityQueue(pq) {
/** insert key ordering with [[PriorityQueue.greater]] */
def insert(key: A): Unit = insert(key, greater)
/** remove min element */
def pop(): Option[A] = pop(greater)
/** check parent and children are in proper indexes */
def isMinHeap(): Boolean = checkHeap(greater)
/** return keys in ascending sorted order */
def keys(): Seq[A] = pq.sorted[A]
/** return keys as string */
override def toString(): String = toString(keys)
}
