SSSP

Summary

SSSP algorithms

SSSP related problems

• single-destination shortest path(multiple sources) -> SSSP on transposed AL
• single-source single-destination shortest path -> early termination, dijkstra’s invariant
• kth shortest path -> dijkstra with PQ of distances, revisit

Concept

Single-source shortest path(SSSP)

• shortest path(smallest weight) from any source node to the other node visitable from the source
• SSSP is not unique, is the graph is not a tree, there may be multiple paths to same node
• 6 vertex cyclic graph: SSSP from 0 to 5

Shortest path spanning tree

• has the source-node as the root
• may not span all nodes, since not all nodes are necessarily visitable by all other nodes
• 6 vertex cyclic graph: SSSP spanning tree from 0

Negative weight cycles

• poor definition on how to handle them
• can lead to infinite looping
• 3 vertex -ve cycle

negative weights are not in the cs2040s syllabus

Edge relaxation

• check if an incoming edge results in a shorter path

if (dist[v] > dist[u] + w) { // if using this edge can give v a shorter distance
	dist[v] = dist[u] + w; // "relax" the edge
	p[v] = u; // update parent array	
} 

• 3 vertex DAG: relax 1 -> 2

Infinity

• to employ relaxation, all the distances must be initialised to infinity(a very big number)
• can use Integer.MAX_VALUE, but we risk overflowing if we add

int INF = 1e9;

List<Integer> dist = new ArrayList<>(Collections.nCopies(V, INF));
dist.set(s, 0); // distance to source from source = 0

Simple path

• a shortest path(with no negative edges) is a simple path
• there are no cycles in a shortest path

BFS method

• only on uniform +ve weights/unweighted graph
• counting the least number of jumps

DFS method

• DFS finds the first path to any visitable node
• correctness is only garunteed when there is only 1 path to any node

Dynamic Programming

• given a DAG
• topological sort + one pass Bellman-Ford

Application

Leetcode: Cheapest Flights Within K Stops

• per-level BFS
• care about jumps not weights

List<List<int[]>> AL = new ArrayList<>();
for (int i = 0; i < n; i++)
	AL.add(new ArrayList<>());

for (int[] e : flights) // directed edges
	AL.get(e[0]).add(new int[] { e[1], e[2] });

int INF = 1000000000;
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[src] = 0;

// BFS by level
Queue<int[]> q = new LinkedList<>();
q.add(new int[] { src, 0 }); // [u, d]

while (!q.isEmpty() && k-- >= 0) { // if k = 0, one jump to dst
	// each iteration level/jump from src
	int sz = q.size(); // important, we only want to go through the number of nodes in this level
	for (int i = 0; i < sz; i++) {
		int[] u_d = q.poll();

		for (int[] v_w : AL.get(u_d[0])) {
			int v = v_w[0];
			int d = u_d[1] + v_w[1];
			if (d < dist[v]) {
				dist[v] = d;
				q.add(new int[] { v, d });
			}
		}
	}
}

return dist[dst] == INF ? -1 : dist[dst];