Generate a Connected Graph and Find a Shortest Path
Problem statement
Generate a connected, undirected, unweighted graph with n nodes numbered 0 through n-1, then find a shortest path from source to target. The graph must be generated from the supplied seed; it is not a graph supplied as input.
For this exercise, use this exact pseudorandom construction so a run is reproducible:
- Set state=seed. Each random draw replaces state with
(1103515245*state+12345) mod 2147483648and returns that new state. Compute the multiplication exactly. - For v=1,2,...,n-1, draw once, set u=draw mod v, and add the undirected edge u-v. These edges connect each new node to an earlier node.
- Visit every pair (u,v) with u<v in increasing u, then increasing v. Skip an edge already present without drawing. Otherwise draw once and add the edge exactly when draw mod 4 equals zero.
For this exercise, return an array with n+1 rows. Rows 0 through n-1 are the generated adjacency lists, each sorted by increasing neighbor ID. The final row is the lexicographically smallest shortest path from source to target, including both endpoints. Equal endpoints give a one-node path. There are no self-loops or duplicate edges.
The seed, generator, extra-edge rule, path tie rule and returned representation are practice choices omitted by the report. A caller can vary the seed for different runs; the same seed reproduces the same graph and different seeds may still produce the same graph. This is not a uniform sampler over all connected graphs.
Function
randomGraphPath(n: int, source: int, target: int, seed: int) → int[][]Examples
Example 1
n = 4source = 0target = 3seed = 0return = [[1,2,3],[0],[0,3],[0,2],[0,3]]The parent-stage draws are 12345, 1406932606 and 654583775, giving edges 0-1, 0-2 and 2-3. Of the remaining pairs, only 0-3 is added. The adjacency rows are [1,2,3], [0], [0,3] and [0,2]. The added edge gives shortest path [0,3].
Example 2
n = 3source = 1target = 2seed = 0return = [[1,2],[0],[0],[1,0,2]]The parent stage creates edges 0-1 and 0-2, and the remaining pair 1-2 is not added. The adjacency rows are [1,2], [0] and [0]. From node 1 to node 2, return path [1,0,2] after those rows.
Constraints
1 <= n <= 1000 <= source < nand0 <= target < n0 <= seed <= 2147483647