Notes from CS2040S Week 10 Lecture 1 on Shortest Path Algorithms

cs2040s_w10_l1.md

CS2040s Week 10 Lecture 1

Notes from CS2040S Week 10 Lecture 1 on Shortest Path Algorithms

Edge Weights

• Edges have weights on them that represent cost of traversal
  • Could be distance, money, energy needed
• Shortest path isn't necessarily the shortest
  • It's the path with the minimal total weight

Questions

• How far is it from S to D
• What is the shortest path from S to D
• Find the shortest path from S to every node
• Find the shortest path between every pair of nodes

We cannot use BFS since it finds the path with minimal number of hops, not minimal total weight/distance.

Triangle Inequality

• Shortests path follows the Triangle Inequality

D(S, C) <= D(S, A) + S(A, C)

Bellman-Ford

• Maintain estimate for each distance
  • Start by assuming it's infinite

int[] dist = new int[V.length]
Arrays.fill(dist, INFTY)
dist[0] = 0

• The goal is to reduce the estimates
  • An invariant is that the estimate >= distance
• We relax an edge R(S, A)
  • Update the estimate using triangle inquality
• We can ignore a new edge if the current relaxed value is smaller than the new edge weight

relax(int u, int v):
	if (dist[v] > dist[u] + weight(u, v):
		dist[v] = dist[u] + weight(u, v)

/*
we can't do this simply since we have to
relax the same edge V-1 times in some cases.

ORDER MATTERS to ensure minimal relaxation.
*/
for (Edge e : graph):
	relax(e)

The goal is to relax the edges in a specific nodes.

n = V.length
for (i = 0; i < n; i++): // O(V)
	for (Edge e : graph): // O(E)
		relax(e) // O(VE)

To terminate the process early, we have to monitor for a sequence of |E| relax operations having no effect.

Runtime of Bellman-Ford is O(VE).

Why does Bellman-Ford work?

• Makes 1 hop worth of progress each time
• After x iterations of outer loop, x hop estimate after relaxation is correct
  • V-1 iterations are enough to get a good estimation
• For negative weight cycles, there is no shortest path since it'll get stuck in an infinite loop

If P is the shortest path from S to D, and if P goes through some X, then P is also the shortest path from S to X and from X to D. Any subpath of a shortest path will also be a shortest path.

To detect cycles, run Bellman-Ford for |V| iterations - If an estimate changes in the last iteration, then negative weight cycle exists

Same Weight Graphs

• What if the graph has all equal weights?
  • Just use BFS

Bellman-Ford Summary

• Repeat |V| times: relax every edge in the right order
• Stop when "converges"
• O(VE)
• Relaxation can take place in any order we want
• For undirected graphs, split the undirected edge into two directed edges
  • Doesn't work with negative weight edge since splitting creates a negative weight cycle
• Between two nodes with weight 10, you can create fake nodes in between of weight 1
  • 10 = 1 + 1 + 1 + .... + 1 + 1
  • Becomes equal cost undirected graph
  • Just use BFS then
  • Not a great solution

Faster Algorithm

• Relax edges in the "right" order
• O(E) cost for relaxation step
  • Extending a path does not make it shorter
  • All edge weights >= 0

Dijkstra's Algorithm

• Relax the shortest edge first
  • Maintain distance estimate for every node
  • Begin with empty shortest path tree
  • Repeat
    • Consider vertex with minimum estimate
    • Add vertext to shortest path tree
    • Relax all outgoing edges
• AVL Tree can be used to store vertices/distances
  • Maintain distances in sorted order
• Runtime is O(E logV)
  • For each node, look at it only once
  • Each edge is relaxed only once – O(E) since |E| times
  • Priority Queue operation are O(logV)
  • insert/deleteMin happens |V| times
    • Each node is added to the queue once
  • Total runtime is O((V+E) log V) = O(E logV) with AVL Tree
• Every "finished" vertex has correct estimate
• Initially, only the start node is in the "finished" set
• Extending a path does not make it shorter
  • No negative weights allowed (positive only)
• Reweighting (by translating every edge by k) does not work
  • Changes the shortest path

Early Stopping

• We can stop as soon as we dequeue the destination
  • As an item is removed from the queue, that node is done
  • That node will never be relaxed again
  • Dequeued = Finished

Performance Array: O(V^2) AVL Tree: O(E log V) d-way Heap: O(E logV) with log base E/V Fibonacci Heap: O(E + VlogV)

Invariant

// assuming graph G and priority queue pq 
searchPath(int start):
	pq.insert(start, 0)
	distTo = new double[G.size()]
	Arrays.fill(fistTo, INFTY)
	distTo[start] = 0
	
	while (!pq.isEmpty()):
		int w = pq.deleteMin()
		for (Edge e : G[w].nbors):
			relax(e)

relax(Edge e):
	int v = e.from()
	int w = e.to()
	double weight = e.weight()
	if (distTo[w] > distTo[v] + weight):
		distTo[w] = distTo[v] + weight
		parent[w] = v;

		if (pq.contains(w)):
			pq.decreaseKey(w, distTo[w])
		else:
			pq.insert(w, distTo[w])

AVL Tree

• Indexed by priority
• Existing methods
  • deleteMin() O(logn)
  • insert(key, priority) O(logn)
  • contains(key) O(1)
  • decreaseKey(key, priority) O(logn)