<aside> <img src="https://super.so/icon/dark/star.svg" alt="https://super.so/icon/dark/star.svg" width="40px" /> Dijkstra’s Algorithm has been rewritten: New Version

</aside>

We can either use priority queue or array

Basic opertaion complexities

• Priority queue
  • Extract min: $O(\log n)$
  • Update value: $O(\log n)$
• Array
  • Extract min: $O(n)$
  • Update value: $O(1)$ (with given position)

Pseudocode

// @param {node} s: source node
// @param {graph} G: graph received as adjacency list
Dijkstra(G(V, E, W), s) {
	// initialization
	for (each v in V) {
		d[v] = ∞; 
		pi[v] = null;
	}
	d[s] = 0;
	let Q = build_priority_queue(V); // or build array with the d[] array
	while (!Q.isEmpty()) {
		u = Q.Extract_Min(); 
		// priority queue will call pop()
		// array will do linear scan

		for (each v in Adj[u]) {
			if (d[v] > d[u] + W(u, v)) { // can the new path bring improvement?
				d[v] = d[u] + W(u, v); // update with each ADT's method
				pi[v] = u;
			}
		}
	}
}

Priority Queue

$\boxed{\text{EX.1}}$ Priority Queue

Example at 13:48

Array

We will have an array $Q=d$ with size m

So the Extract_Min(Q) will be $O(m)$

In the if statement:

if (d[v] > d[u] + W(u, v)) { // can the new path bring improvement?
	d[v] = d[u] + W(u, v);
	Q[v] = d[v]; // also update Q
	pi[v] = u;
}

$\boxed{\text{EX.2}}$ Array

G:

$$ \begin{array}{c|cccc} &s & a & b & c\\ \hline d & 0 & \infin & \infin&\infin

\\\pi &\empty&\empty&\empty&\empty

\end{array} $$