Shortest Paths with Unweighted Edges

Unweighted Shortest Path

Solution - Message Route

Time Complexity: $\mathcal{O}(V+E)$

We can observe is that there are many possible shortest paths to output. Fortunately, the problem states that we can print any valid solution. Notice that like every other BFS problem, the distance of each node increases by $1$ when we travel to the next level of unvisited nodes. However, the problem requires that we add additional information - in this case, the path. When we traverse from node $a$ to $b$, we can set the parent of $b$ to $a$. After the BFS is complete, this allows us to backtrack through the parents which ultimately leads us to our starting node. We know to terminate at node $1$ because it's the starting node. If there is no path to our end node, then its distance will remain at INT_MAX.

For the test input, we start with the following parent array.

After visiting children of node $1$:

After visiting node $5$ from node $4$:

To determine the path, we can backtrack from node $n \rightarrow 1$, in this case $5 \rightarrow 1$, pushing each value that we backtrack into a vector. The path we take is $5 \rightarrow \texttt{parent}[5]=4 \rightarrow \texttt{parent}[4] =1$ which corresponds to the vector $[5, 4, 1]$. We break at node $1$ because it was the initial starting node. Finally, we reverse the vector and print out its length (in this case, $3$).

Copy
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
#define pb push_back

int main() {
	int N, M;
	cin >> N >> M;
	vi dist(N + 1, INT_MAX), parent(N + 1);

Copy
import java.io.*;
import java.util.*;

public class Solution {
 	Code Snippet: Kattio (Click to expand)

	private static Map<Integer, LinkedList<Integer>> adj = new HashMap<>();

	public static void main(String[] args) {
		Kattio io = new Kattio();

Extension - 0/1 BFS

A 0/1 BFS finds the shortest path in a graph where the weights on the edges can only be 0 or 1, and runs in $\mathcal{O}(V + E)$ using a deque. Read the resource below for an explanation of how the algorithm works.

Solution - Tracks in the Snow

Complexity: $\mathcal O(NM)$

We can use the following greedy strategy to find our answer:

• Run flood fill to find each connected component with the same tracks.
• Construct a graph where the nodes are the connected components and there are edges between adjacent connected components.
• The answer is the maximum distance from the node containing $(1, 1)$ to another node. We can use BFS to find this distance.

For a detailed proof of why this works, see the official editorial.

Although this gives us an $\mathcal O(NM)$ solution, there is a simpler solution using 0/1 BFS!

Consider the graph with an edge between each pair of adjacent cells with tracks, where the weight is 0 if the tracks are the same and 1 otherwise. The answer is simply the longest shortest-path from the top left cell. This is because going from one track to another same one is like not leaving a node (hence the cost is $0$), while going from one track to a different one is like traversing the edge between two nodes (hence the cost is $1$).

Since the weight of each edge is either 0 or 1 and we want the shortest paths from the top left cell to each other cell, we can apply 0/1 BFS. The time complexity of this solution is $\mathcal O(NM)$.

Copy
#include <bits/stdc++.h>
using namespace std;

int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};

int n, m, depth[4000][4000], ans = 1;
string snow[4000];

bool inside(int x, int y) {
	return (x > -1 && x < n && y > -1 && y < m && snow[x][y] != '.');

Copy
import java.io.*;
import java.util.*;

public class tracks {
	static final int[] dx = {0, 0, -1, 1};
	static final int[] dy = {-1, 1, 0, 0};
	static int N = 1, H, W;
	static int[][] grid, count;
	public static void main(String[] args) {
		FastIO io = new FastIO();

Problems