dijkstra's algorithm

Work in Progress

Summary

Dijkstra’s algorithm

greedy

Time complexity

average case:
best case:
any directed tree: dijkstra(0)

Modified dijkstra

worse case: - each propagation is , upto propagations
repeated repropagation: dijkstra(0)

Invariant

with +ve weights only
at each iteration, the nodes that have been “settled” by the algorithm will have the correct shortest path
can support -ve weights at the cost of the invariant

for SSSDSP with +ve weight, we can terminate once the destination has been vsited

Concept

Algorithm

sort the verticies according to distance from the source
greedily relax outgoing edges from the vertex with the lowest distance
once a vertex has been “settled” assume it has the shortest path, do not relax it again

java

void dijkstra(int s) { // O(V log V + E log V) = O((V+E) log V)
	dist.set(s, 0);
	
	TreeSet<int[]> pq = new TreeSet<>(Comparator.comparingInt(x -> x[1])); // balanced BST, bineary heap works as well
	for (int u = 0; u < V; ++u) // enqueue all verticies -> O(V log V)
		pq.add(new int[] { u, dist.get(u) }); // add [ v, d ] -> O(log V)

	while (!pq.isEmpty()) { // every vertex, k neighbours are relaxed -> O(E log V)
		int[] min = pq.pollFirst(); // node to be relaxed
		int u = min[0];
		
		// present in VisuAlgo
		if (visited.get(u)) continue; // already settled, skip
		visited.set(u, true);
		
		for (int[] v_w : AL.get(u)) { // e = [ v, w ]
			int v = v_w[0];
			int w = v_w[1];
			
			// absent in VisuAlgo
			// if (visited.get(v)) continue; // already settled, skip
			
			if (dist.get(u) + w >= dist.get(v)) 
				continue; // not improving, skip
			pq.remove(new int[] { v, dist.get(v) }); // erase old [ v, d ] -> O(log V)
			dist.set(v, dist.get(u) + w); // relax operation
			pq.add(new int[] { v, dist.get(v) }); // enqueue better [ v, d ] -> O(log V)
		}
	}
}

6 vertex cyclic graph: dijkstra(0)

curr | pq
_    | [0, 0], [1, INF], [2, INF], [3, INF], [4, INF], [5, INF]
0    | [1, 1], [2, 5], [3, INF], [4, INF], [5, INF]
1    | [4, 2], [2, 3], [3, 3], [5, INF]
4    | [2, 3], [3, 3], [5, 4]
2    | [3, 3], [5, 4]
3    | [5, 4]
5    | _

verticies are only visited once, which can cause problems when the first visit is not the shortest distance

Negative weights

alternate path might result in shorter distance
shorter distance is not propagated
4-pan -ve weight: dijkstra(0)

curr | pq
_    | [0, 0], [1, INF], [2, INF], [3, INF], [4, INF]
0    | [1, 1], [2, 10], [3, INF], [4, INF]
1    | [3, 3], [2, 10], [4, INF]
3    | [4, 6], [2, 10]
4    | [2, 10]
2    | [3, 0]
3    | _  <- already settled, VisuAlgo relaxes it but doesn't propagate further

slightly different implementations of the original dijkstra will result in different outcomes

include both/the first visited check -> incorrect SSSP and violates invariant

without the visited checks -> correct SSSP, nodes may be relaxed multiple times but invariant violated

Modified algorithm

to support negative weight
BFS with a priority queue(min weight) instead
deteriorates to PQ + Bellman-Ford

java

void dijkstra(int s) { // O(V log V + E log V) = O((V+E) log V)
	dist.set(s, 0);
	
	PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x[1])); 
	pq.offer(new int[] { s, 0 }); // only the source is added
	
	while (!pq.isEmpty()) { // every vertex and every edge are relaxed -> O((V+E) log V)
		int[] min = pq.poll(); // node to be relaxed
		int u = min[0];
		
		for (int[] v_w : AL.get(u)) { // e = [ v, w ]
			int v = v_w[0];
			int w = v_w[1];
			
			if (dist.get(u) + w >= dist.get(v)) 
				continue; // not improving, skip

			dist.set(v, dist.get(u) + w); // relax operation
			pq.offer(new int[] { v, dist.get(v) }); // enqueue better [ v, d ] -> O(log E) = O(log V^2) = O(log V)
		}
	}
}

4-pan -ve weight: dijkstra(0)

curr | pq
_    | [0, 0]
0    | [1, 1], [2, 10]
1    | [3, 3], [2, 10]
3    | [4, 6], [2, 10]
4    | [2, 10]
2    | [3, 0]
3    | [4, 3] <- propagated further
4    | _

correct SSSP but invariant is violated

Application

Leetcode: Network Delay Time

1-indexing
max of all SSSPs

java

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

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

int INF = 1000000000;

List<Integer> dist = new ArrayList<>(Collections.nCopies(n + 1, INF));
dist.set(0, 0); // ignore the 0th node
dist.set(k, 0);

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));
pq.offer(new int[] { k, 0 });

while (!pq.isEmpty()) {
	int[] min = pq.poll();
	int u = min[0];

	for (int[] v_w : AL.get(u)) { // e = [ v, w ]
		int v = v_w[0];
		int w = v_w[1];

		if (dist.get(u) + w >= dist.get(v))
			continue; // not improving, skip

		dist.set(v, dist.get(u) + w); // relax operation
		pq.offer(new int[] { v, dist.get(v) });
	}
}

Collections.sort(dist); // O(V log V)
int max = dist.get(n);
return max == INF ? -1 : max;

Kattis: Vacation Time

SSSP from source and destination, bidirectional search
meet in the middle with selected edge

java

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);

StringTokenizer st = new StringTokenizer(br.readLine());

int a = Integer.parseInt(st.nextToken()), f = Integer.parseInt(st.nextToken());

ArrayList<ArrayList<int[]>> AL = new ArrayList<>();
ArrayList<ArrayList<int[]>> rev = new ArrayList<>();
ArrayList<int[]> edges = new ArrayList<>();
for (int u = 0; u < a; ++u) {
	AL.add(new ArrayList<>());
	rev.add(new ArrayList<>());
}

while (f-- > 0) {
	st = new StringTokenizer(br.readLine());
	int o = Integer.parseInt(st.nextToken()), d = Integer.parseInt(st.nextToken()),
			c = Integer.parseInt(st.nextToken());
	String m = st.nextToken();
	AL.get(o).add(new int[] { d, c });
	rev.get(d).add(new int[] { o, c });
	if (m.equals("A380"))
		edges.add(new int[] { o, d, c });
}

int INF = 1000000000;
ArrayList<Integer> distS = new ArrayList<>();
ArrayList<Integer> distT = new ArrayList<>();
for (int i = 0; i < a; i++) {
	distS.add(INF);
	distT.add(INF);
}
distS.set(0, 0); // start from 0
distT.set(a - 1, 0); // start from a - 1

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(i -> i[0]));
pq.add(new int[] { 0, 0 }); // [dist, u]

while (!pq.isEmpty()) {
	int[] top = pq.poll();
	int u = top[1];
	for (int[] next : AL.get(u)) {
		int v = next[0], w = next[1];
		if (distS.get(u) + w >= distS.get(v))
			continue;
		distS.set(v, distS.get(u) + w);
		pq.add(new int[] { distS.get(v), v });
	}
}

pq.clear();
pq.add(new int[] { 0, a - 1 }); // [dist, u]

while (!pq.isEmpty()) {
	int[] top = pq.poll();
	int u = top[1];
	for (int[] next : rev.get(u)) {
		int v = next[0], w = next[1];
		if (distT.get(u) + w >= distT.get(v))
			continue;
		distT.set(v, distT.get(u) + w);
		pq.add(new int[] { distT.get(v), v });
	}
}

int min = INF;
for (int i = 0; i < edges.size(); i++) {
	int[] e = edges.get(i);
	min = Math.min(min, distS.get(e[0]) + distT.get(e[1]) + e[2]);
}

pw.println(min == INF ? -1 : min);
pw.close();

Leetcode: Minumum Time to Visit Disappearing Nodes

java

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

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

int INF = 1000000000;
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[0] = 0; // 0 is the source
// disappear[0] >= 1, so no edge case here

boolean[] visited = new boolean[n];
Arrays.fill(visited, false);

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));
pq.offer(new int[] { 0, 0 });

while (!pq.isEmpty()) {
	int[] min = pq.poll();
	int u = min[0];

	if (visited[u]) // avoid revisiting nodes
		continue;
	visited[u] = true;

	if (dist[u] >= disappear[u])
		continue;

	for (int[] v_w : AL.get(u)) { // e = [ v, w ]
		int v = v_w[0];
		int w = v_w[1];

		int r = dist[u] + w;
		if (r >= disappear[v] || r >= dist[v]) // if the resulting distance is >= to the time it disappears
			continue; // not improving, skip

		dist[v] = r; // relax operation
		pq.offer(new int[] { v, dist[v] });
	}
}

for (int i = 0; i < n; i++)
	if (dist[i] == INF)
		dist[i] = -1;

return dist;
}

Leetcode: Number of Ways to Arrive at Destination

number of shortests paths
count paths modification
better solution using BFS

java

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

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

long INF = Long.MAX_VALUE;
long[] dist = new long[n];
Arrays.fill(dist, INF);
dist[0] = 0;

int[] ways = new int[n]; // keep track of number of ways to each node
Arrays.fill(ways, 0);
ways[0] = 1; // only 1 way to source

PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(x -> x[1]));
pq.offer(new long[] { 0, 0 });

while (!pq.isEmpty()) {
	long[] min = pq.poll();
	int u = (int) min[0];

	if (min[1] > dist[u]) // distance is not the mimimum, no point checking
		continue;

	for (int[] v_w : AL.get(u)) { // e = [ v, w ]
		int v = v_w[0];
		int w = v_w[1];

		if (v == n-1) System.out.println("here");

		if (dist[u] + w < dist[v]) {
			dist[v] = dist[u] + w; // relax operation
			ways[v] = ways[u]; // replace the number of ways
			pq.offer(new long[] { v, dist[v] });
		} else if (dist[u] + w == dist[v]) { // alr visited with same distance, add the ways
			ways[v] = (ways[v] + ways[u]) % (1000000000 + 7);
		}
	}
}
return ways[n - 1];

Leetcode: Cheapest Flights Within K Stops

SSSP by jumps, accumulate distance
early termination once destination is reached

java

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[] jmps = new int[n];
Arrays.fill(jmps, INF);
jmps[src] = 0;

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));
pq.offer(new int[] { src, 0, 0 });

while (!pq.isEmpty()) {
	int[] min = pq.poll();
	int u = min[0];
	int d = min[1];
	int j = min[2];

	if (u == dst)
		return min[1]; // early termination

	// overall least jumps, SSSP by jumps
	if (j > k || j > jmps[u]) // skip if more than k jumps are needed or there is a path with less jumps to this node
		continue;

	jmps[u] = j;

	for (int[] v_w : AL.get(u)) { // e = [ v, w ]
		int v = v_w[0];
		int w = v_w[1];

		//don't care about getting the overall shortest path
		pq.offer(new int[] { v, min[1] + w, j + 1 }); // implicit relax operation
	}
}

return -1;

dijkstra's algorithm

Summary

Concept

Application

Extra