Shortest-Path Algorithms

Dijkstra’s Algorithm

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

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 $\infty$ 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});
	}
}

Is the processed list really needed?

Not really, it helps speed. The if statement only adds nodes again for edges that reduce distance, but by adding the processed list, you avoid going through the entire edges again.

The computational complexity of Dijkstra’s Algorithm is $O((n+e)\log n)$.

Python (uses heapq)

• https://realpython.com/python-heapq-module/
• https://builtin.com/software-engineering-perspectives/dijkstras-algorithm

def dijkstra(graph,source):
  nodes={}
  for node in graph:
      nodes[node]=Node()
  nodes[source].d=0
  queue=[(0,source)] #priority queue
  while queue:
      d,node=heapq.heappop(queue)
      if nodes[node].finished:
          continue
      nodes[node].finished=True
      for neighbor in graph[node]:
          if nodes[neighbor].finished:
              continue
          new_d=d+graph[node][neighbor]
          if new_d<nodes[neighbor].d:
              nodes[neighbor].d=new_d
              nodes[neighbor].parent=node
              heapq.heappush(queue,(new_d,neighbor))
  return nodes

Complexity Analysis

From CS341 class.

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.

• TODO: show counter-example?

The proof of correctness goes along the lines of a contradiction. In my own words:

$\delta (s,x)$ is the shortest distance from $s$ to $x$ .

Let $s$ be the source vertex Let $s$ be the source vertex. Assume $u$ is the first vertex where $d[u]\ne \delta (s,u)$ is not set correctly. Let time $t$ be the time when $u$ is added to $C$. We let $P$ be the actually shortest path from $s$ to $u$.

On this path $P$, we use 2 vertices: $x$ and $y$. We define $y$ as the first vertex in $V-C$ on path $P$. Let $x$ be the predecessor of $y$.

• At time $t$, we have $d[y]=\delta (s,y)$
  • for the case where $y=u$, then can you still make the argument?
  • We make the argument by talking about $x$

When $x$ was visited and added to $C$,

• $d[x]=\delta (s,x)$ is correct
• its neighbours are added, and $y$ is a neighbours, so $d[y]=min(d[y],d[x]+w(x,y))=\delta (s,x)+w(x,y)=\delta (s,y)$

How can you argue that $\delta (s,x)+w(x,y)=\delta (s,y)$? Because $x$ and $y$ are on the shortest path from $s$ to $u$, so $s-x$ connected by $y$ is a shortest path too.

• But what if there is another path from $x$ to $y$? IDK, like there can be multiple paths
• Like the case in the image below, where the edge directly connect $x$ to $y$ is not the shortest path.
• Then $y$ doesn’t actually satisfy the initial definition

We have vertices $x$ and $y$, $x$ in $C$, $y$ not in $C$. $d[x]=\delta (s,x)$ is correct at time $t$.

What is s is directly connected to u?

Then you can define $s=x$, $y=u$.

Related

• Bellman-Ford Algorithm