Shortest Cycle
You're at a city. You leave on some road, wander through the network, and come back. What's the cheapest round trip? What if you need to find the shortest cycle in the entire graph?
These problems seem like standard shortest-path questions. But the target is the source. That twist changes everything.
The Problem: ABC191-E Come Back Quickly
\(N\) cities, \(M\) directed roads with positive weights. For each city \(i\), find the minimum total cost to start at \(i\), traverse at least one road, and return to \(i\). If impossible, output \(-1\).
Why Standard Dijkstra Doesn't Directly Work
You might think: run Dijkstra from city \(s\), then read \(\text{dist}[s]\). But Dijkstra initializes \(\text{dist}[s] = 0\) and never updates it. The source is already "settled" at distance 0 before any relaxation happens.
You need the shortest path from \(s\) back to \(s\) using at least one edge. That means you can't let the source settle immediately.
The Fix: Expand From Neighbors
Instead of initializing \(\text{dist}[s] = 0\), push all of \(s\)'s neighbors into the priority queue with their edge weights. Then run Dijkstra normally. When you eventually reach \(s\) again, that's your shortest cycle.
auto shortest_cycle = [&](int s) -> ll {
vector<ll> dist(N + 1, LLONG_MAX);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
// Self-loop check
for (auto [v, w] : adj[s]) {
if (v == s) return w;
if (w < dist[v]) {
dist[v] = w;
pq.push({w, v});
}
}
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
if (u == s) return d; // found cycle back to s
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return -1; // no cycle through s
};
Gotcha. Don't forget self-loops. If there's an edge \(s \to s\) with weight \(w\), that's immediately a valid cycle. Check before entering the main loop.
Trace: 4-Node Directed Graph
Nodes: 1, 2, 3, 4.
Edges: 1->2 (w=3), 2->3 (w=1), 3->1 (w=2), 2->4 (w=5), 4->1 (w=1).
Finding shortest cycle from node 1:
| Step | Pop | Action | dist[] updates | PQ after |
|---|---|---|---|---|
| init | -- | Push neighbors of 1 | dist[2]=3 | [(3,2)] |
| 1 | (3,2) | Expand 2: edges to 3,4 | dist[3]=4, dist[4]=8 | [(4,3),(8,4)] |
| 2 | (4,3) | Expand 3: edge to 1 | dist[1]=6 | [(6,1),(8,4)] |
| 3 | (6,1) | u==s, return 6 | -- | -- |
Shortest cycle from 1: cost 6 (path: 1->2->3->1, cost 3+1+2=6).
Alternative: 1->2->4->1 costs 3+5+1=9. Longer.
Finding shortest cycle from node 4:
| Step | Pop | Action | dist[] updates | PQ after |
|---|---|---|---|---|
| init | -- | Push neighbors of 4 | dist[1]=1 | [(1,1)] |
| 1 | (1,1) | Expand 1: edge to 2 | dist[2]=4 | [(4,2)] |
| 2 | (4,2) | Expand 2: edges to 3,4 | dist[3]=5, dist[4]=9 | [(5,3),(9,4)] |
| 3 | (5,3) | Expand 3: edge to 1 (already settled) | -- | [(9,4)] |
| 4 | (9,4) | u==s, return 9 | -- | -- |
Shortest cycle from 4: cost 9 (path: 4->1->2->4).
Full Solution: ABC191-E
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int N, M;
cin >> N >> M;
vector<vector<pair<int,ll>>> adj(N + 1);
for (int i = 0; i < M; i++) {
int u, v; ll w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
}
for (int s = 1; s <= N; s++) {
vector<ll> dist(N + 1, LLONG_MAX);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
bool self_loop = false;
ll self_w = LLONG_MAX;
for (auto [v, w] : adj[s]) {
if (v == s) { self_loop = true; self_w = min(self_w, w); continue; }
if (w < dist[v]) {
dist[v] = w;
pq.push({w, v});
}
}
ll ans = self_loop ? self_w : LLONG_MAX;
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
if (u == s) { ans = min(ans, d); break; }
if (d >= ans) break; // prune: can't improve
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
cout << (ans == LLONG_MAX ? -1 : ans) << "\n";
}
return 0;
}
Complexity: \(O(N \cdot (N + M) \log N)\). With \(N, M \leq 2000\), this is fast.
Shortest Cycle in the Entire Graph
ABC376-D Cycle (Directed)
Find the shortest directed cycle in a graph, measured by number of edges.
Run BFS from each node. For source \(s\), use the same trick: initialize BFS from \(s\)'s neighbors. The first time you reach \(s\) again is the shortest cycle through \(s\).
The global shortest cycle is the minimum over all sources.
int shortest = INT_MAX;
for (int s = 1; s <= N; s++) {
vector<int> dist(N + 1, -1);
queue<int> q;
for (int v : adj[s]) {
if (v == s) { shortest = 1; goto done; }
if (dist[v] == -1) {
dist[v] = 1;
q.push(v);
}
}
while (!q.empty()) {
int u = q.front(); q.pop();
if (u == s) { shortest = min(shortest, dist[u]); break; }
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}
done:
Key insight. For directed graphs, you must try every node as a potential cycle root. There's no shortcut like bridge-finding.
Graph Girth (Undirected): CSES and ABC022-C
The girth of a graph is the length of its shortest cycle. For undirected unweighted graphs, there's a cleaner approach than running the "expand from neighbors" trick.
BFS from each node. During BFS from \(s\), if you encounter an edge \((u, v)\) where \(v\) is already visited and \(\text{depth}[v] \geq \text{depth}[u]\), you've found a cycle of length \(\text{depth}[u] + \text{depth}[v] + 1\).
int girth = INT_MAX;
for (int s = 1; s <= N; s++) {
vector<int> depth(N + 1, -1);
depth[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (depth[v] == -1) {
depth[v] = depth[u] + 1;
q.push(v);
} else if (depth[v] >= depth[u]) {
girth = min(girth, depth[u] + depth[v] + 1);
}
}
}
}
Why does this work? BFS builds a spanning tree. Any non-tree edge \((u, v)\) creates a cycle through the BFS tree. The cycle length is \(\text{depth}[u] + \text{depth}[v] + 1\) (go up from \(u\) to their common ancestor, then down to \(v\), then the edge back).
The condition \(\text{depth}[v] \geq \text{depth}[u]\) avoids double-counting the parent edge. If \(\text{depth}[v] < \text{depth}[u]\), this is just the tree edge in reverse.
Gotcha. This only works for unweighted undirected graphs. For weighted graphs, you need the Dijkstra-based approach. For directed graphs, you need per-node BFS/Dijkstra with the neighbor-initialization trick.
ABC022-C Blue Bird: Shortest Cycle Through Node 1
Find the shortest cycle that passes through node 1 in an undirected weighted graph. This is exactly the "shortest cycle from a specific node" problem.
Run Dijkstra from node 1 using the neighbor-initialization trick. The answer is the shortest path that returns to node 1.
// Same Dijkstra trick, but only for s = 1
vector<ll> dist(N + 1, LLONG_MAX);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
for (auto [v, w] : adj[1]) {
if (w < dist[v]) {
dist[v] = w;
pq.push({w, v});
}
}
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
if (u == 1) { cout << d << "\n"; return 0; }
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
cout << -1 << "\n";
Comparing the Approaches
| Problem type | Graph type | Algorithm | Complexity |
|---|---|---|---|
| Shortest cycle through node \(s\) | Directed, weighted | Dijkstra from \(s\)'s neighbors | \(O((N+M) \log N)\) |
| Shortest cycle through node \(s\) | Undirected, unweighted | BFS from \(s\)'s neighbors | \(O(N+M)\) |
| Shortest cycle in graph (girth) | Undirected, unweighted | BFS from every node | \(O(N(N+M))\) |
| Shortest cycle in graph | Directed, unweighted | BFS from every node | \(O(N(N+M))\) |
| Shortest cycle in graph | Weighted | Dijkstra from every node | \(O(N(N+M) \log N)\) |
Key insight. The core trick is always the same: don't let the source settle at distance 0. Either initialize from the source's neighbors, or check for back-edges during BFS. Everything else is choosing BFS vs. Dijkstra based on weights.
Full Solution: CSES Graph Girth
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
vector<vector<int>> adj(N + 1);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int girth = INT_MAX;
for (int s = 1; s <= N; s++) {
vector<int> depth(N + 1, -1);
depth[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
if (depth[u] + 1 >= girth) continue; // prune
for (int v : adj[u]) {
if (depth[v] == -1) {
depth[v] = depth[u] + 1;
q.push(v);
} else if (depth[v] >= depth[u]) {
girth = min(girth, depth[u] + depth[v] + 1);
}
}
}
}
cout << (girth == INT_MAX ? -1 : girth) << "\n";
return 0;
}
Exercises
-
In an undirected graph, can the girth be found in \(o(N \cdot M)\) time? What's the best known bound?
-
For a DAG (directed acyclic graph), what is the shortest cycle? Why?
-
If you need the shortest even-length cycle, how would you modify the BFS approach?
Problems
| Problem | Link | Difficulty |
|---|---|---|
| ABC191-E -- Come Back Quickly | atcoder.jp/contests/abc191/tasks/abc191_e | Medium |
| ABC376-D -- Cycle | atcoder.jp/contests/abc376/tasks/abc376_d | Medium |
| ABC022-C -- Blue Bird | atcoder.jp/contests/abc022/tasks/abc022_c | Medium |
| CSES -- Graph Girth | cses.fi/problemset/task/1707 | Medium |