Skip to content

Collision Analysis

Two people walk shortest paths in opposite directions. Do they collide? At which vertices? On which edges? This requires understanding not just distances, but the structure of all shortest paths.

The Problem

ARC090-E Avoiding Collision: Two people start simultaneously — one at S walking to T, one at T walking to S. Both travel along some shortest path at speed 1. Count the number of (pathA, pathB) pairs such that they never occupy the same vertex or edge at the same time. Answer modulo 10⁹+7.

Setup: Two Dijkstras + Path Counting

Run Dijkstra from S → dist_S[v] and count_S[v] (number of shortest paths from S to v). Run Dijkstra from T → dist_T[v] and count_T[v].

Let D = dist_S[T] (total shortest distance S→T).

Total shortest-path pairs = count_S[T] × count_T[S] = count_S[T]².

Now subtract pairs that collide.

Collision at a Vertex

Time-expanded collision detection: two agents at same position at same time

Person A arrives at vertex v at time dist_S[v]. Person B arrives at vertex v at time dist_T[v].

They collide at v if they're both there at the same time:

💡 Key insight. Collision at vertex v happens when dist_S[v] == dist_T[v] AND dist_S[v] + dist_T[v] == D. The first condition means they arrive at the same time. The second means v is on a shortest path.

When they collide at v, the number of bad pairs through v = count_S[v] × count_T[v] × count_S[v] × count_T[v]... Wait, let's be precise:

  • Paths from S passing through v and continuing to T: count_S[v] × (paths from v to T on SP DAG).
  • Same for person B.

Actually, the number of colliding pairs at vertex v: - Person A's paths through v: count_S[v] × count_from_v_to_T. - Person B's paths through v: count_T[v] × count_from_v_to_S. - Bad pairs = (count_S[v] × count_v_to_T) × (count_T[v] × count_v_to_S).

Where count_v_to_T = count_T[T] if we think of it as count of SP from v to T = paths that pass through v on the S→T SP DAG.

Simplification: for vertex v on the SP DAG, paths through v = count_S[v] × count_T[v] (from S side). The complementary count works similarly.

Collision on an Edge

Two people can also collide mid-edge. Person A crosses edge (u, v) at time dist_S[u] + w/2. Person B crosses edge (v, u) at time dist_T[v] + w/2. They meet on the edge if these times are equal:

dist_S[u] + w/2 = dist_T[v] + w/2, i.e., dist_S[u] = dist_T[v].

But also: dist_S[u] + w = dist_S[v] (edge on SP DAG from S) and dist_T[v] + w = dist_T[u] (edge on SP DAG from T).

And the meeting time must be D/2 (exactly halfway through the total journey).

The Algorithm

  1. Run Dijkstra from S and T. Count shortest paths.
  2. Total pairs = count_S[T]².
  3. For each vertex v where dist_S[v] + dist_T[v] == D and 2 × dist_S[v] == D: subtract vertex collisions.
  4. For each edge (u,v,w) where dist_S[u] + w + dist_T[v] == D and 2 × dist_S[u] + w == D and w is even (they meet at the midpoint): subtract edge collisions.
  5. Answer = total - vertex_collisions - edge_collisions.

Simpler Problem: ABC148-F Playing Tag on Tree

Problem: Tree with N nodes. Takahashi starts at node s, Aoki at node t. Both move optimally. Can Aoki escape (reach a leaf not blocked by Takahashi)?

This is simpler: BFS from both players. Aoki can reach vertex v before Takahashi if dist_T[v] < dist_S[v]. Aoki wins if any leaf satisfies this.

On a tree (unique paths), this reduces to: find the vertex on the s→t path closest to t where dist_S[v] > dist_T[v]. Aoki can escape past this point.

// BFS from s and t
auto ds = bfs(s, adj, n);
auto dt = bfs(t, adj, n);

// Aoki wins if any leaf v has dt[v] < ds[v]
bool aoki_wins = false;
for (int v = 1; v <= n; v++)
    if (adj[v].size() == 1 && dt[v] < ds[v])
        aoki_wins = true;

The Spectrum of Two-Person Problems

Problem Technique Complexity
Can they meet? Two BFS, compare distances O(V+E)
Where do they meet? Two BFS, find dist_S[v] == dist_T[v] O(V+E)
Do they collide on shortest paths? Two Dijkstras + path counting O(V log V)
Can one escape the other? Two BFS + leaf analysis O(V+E)

Exercises

  1. In Avoiding Collision, what if the graph is unweighted? Does BFS suffice?
  2. For Playing Tag on Tree, what if both players move at different speeds?
  3. Can two people always avoid collision on a shortest path if the graph has multiple shortest paths?

Problems

Problem Link Difficulty
ARC090-E Avoiding Collision atcoder.jp Hard
ABC148-F Playing Tag on Tree atcoder.jp Medium
LC 1976 — Number of Ways leetcode.com Medium