Pattern visualizer

Requirements Met (Prerequisite Tasks)

Each query only asks whether a directed path exists between two tasks, which makes this a reachability problem, not a shortest-path one. Answering queries one at a time means re-searching the graph for every query; instead, build the full n x n transitive closure ONCE — reach[i][j] means i can reach j through any number of hops — and every query becomes a single lookup. Floyd-Warshall does this by trying each node k in turn as a bridge: if i reaches k and k reaches j, then i reaches j too, even with no direct arrow between them. Animated on: 6 tasks with prerequisites 0->1, 1->2, 2->3, 0->4, 4->3, 5->2 (a->b means a before b) — for queries (0,3), (3,0), (5,3), (0,5) and (1,4), must the first task come before the second?.

Floyd-Warshall transitive closure: build reachability once, answer every query in O(1)

time O(V^3 + Q)space O(V^2)step 1 / 11

Direct prerequisites

line 1

6 tasks, and prerequisite [a, b] means a must be done before b. The 5 queries below don't each need their own search — building the full reachability picture ONCE answers all of them in O(1) apiece.

Pseudocode

1FUNCTION checkTasks(n, prereqs, queries):
2  FOR EACH (a, b) IN prereqs
3    reach[a][b] <- true
4  FOR k FROM 0 TO n - 1
5    FOR i FROM 0 TO n - 1
6      FOR j FROM 0 TO n - 1
7        IF reach[i][k] AND reach[k][j]
8          reach[i][j] <- true
9  FOR EACH (u, v) IN queries
10    APPEND reach[u][v] TO answers
11  RETURN answers

← / → step · space play · Home restart

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap