Dijkstra’s Algorithm

Dijkstra’s Algorithm is used for solving single source shortest path problems. In this algorithm, a single node is fixed as a source node and shortest paths from this node to all other nodes in graph is found.

A similar algorithm to BFS can be applied to find the shortest path to arbitrary graphs with nonnegative edge weights. #todo

From CS341

• Why is the inner loop in a heap implementation have a runtime cost of $O(|E|\log |V|)$? Wouldn’t it be $O(|E|)$ since we are only visiting adjacent vertices?
  • Every relaxation requires us to update the distance of the corresponding vertex in the heap, which requires $O(\log |V|)$ time, and we do this at most $O(|E|)$ times, since $u$ has at most $|E|$ neighbours.

Implementation

An efficient implementation of Dijkstra’s algorithm requires that it is possible to efficiently find the minimum distance node that has not been processed. We thus use a Priority Queue so that the next node to be processed can be retrieved in $O(\log n)$.

Graph is stored as adjacency lists so that $adj[a]$ contains a pair $(b,w)$ always when there is an edge from node a to node b with weight w.

The Priority Queue q contains pairs of the form $(-d,x)$, meaning that the current distance to node $x$ is $d$.

• dist[i] is the distance to node i
• processed[i] indicates whether node i has been processed
  • IMPORTANT: Whenever a node is processed, its distance is final.

Initially the distance is 0 to x and ∞ to all other nodes.

for (int i = 1; i <= n; i++) distance[i] = INF; 
distance[x] = 0;
q.push({0,x});
while (!q.empty()) {
	int a = q.top().second; 
	q.pop();
	if (processed[a]) continue;
	processed[a] = true;
	for (auto u : adj[a]) {
		int b = u.first, w = u.second;
		if (distance[a]+w < distance[b]) {
			distance[b] = distance[a]+w;
			q.push({-distance[b],b});
	}
}

What happens if you use a regular queue?

Using a regular queue in Dijkstra’s algorithm instead of a priority queue will not maintain the algorithm’s property of always selecting the next closest vertex to the source. This can lead to incorrect shortest path calculations.

Questions

Why is it beneficial to store the vertices of the graph inside a binary min heap? Couldn't we have used an adjacency list similar to DFS and BFS?

We use a min-heap because we want to explore the vertices with the smallest cost (is that what your question is?)

I’m not sure what an adjacency list has to do with the min-heap since an adjacency list is used to represent a graph, but the min-heap is used to pick what nodes we want to explore.

Why Dijkstra's algorithm doesn't work with negative weights

• Dijkstra’s algorithm employs a greedy strategy, always selecting the vertex with the smallest known distance from the source vertex at each step.
• This strategy assumes that adding a new vertex to the set of vertices with known shortest distances will never result in a shorter path to any vertex than the paths already considered.
• However, in the presence of negative weights, this assumption is violated because the distance to a neighbouring vertex can decrease when traversing an edge with negative weight.
• When negative weights are present, Dijkstra’s algorithm may select a vertex based on the current shortest path information, leading to incorrect shortest path calculations.
• Negative-weight edges can create cycles where repeatedly traversing the cycle reduces the total path weight, violating the assumption made by Dijkstra’s algorithm.
• Negative-weight cycles pose a particularly challenging problem for Dijkstra’s algorithm.
• If a negative-weight cycle exists reachable from the source vertex, it can be traversed repeatedly to produce arbitrarily low total path weights, leading to no well-defined shortest path.
• Dijkstra’s algorithm, which does not account for negative weights, cannot handle this scenario and may produce incorrect results or enter into an infinite loop.