human
Consider an undirected connected graph G = ⟨V, E⟩ with n nodes and
m edges; define a special source node s ∈ V in the graph G. Describe a data structure which can
achieve the following:
• the data structure can be constructed in O(n + m) worst-case time;
• the space consumption of the data structure (excluding the graph G) is O(n) in the worst
case;
• for any query node q ∈ V other than s, it can report the shortest distance between s and q in
the graph G in O(1) worst-case time, where the shortest distance between s and q is defined
as the length, (i.e., the number of edges) of the shortest path from s to q in G.
You will need to justify the above complexities of your algorithm with appropriate analysis.
gpt
--- Reasoning ---
1. Is the question multiple-choice question?
No
2. Is it implied multiple-choice question?
No
3. If two experts were independently asked the question, will the final answer be exactly the same?
No

--- Answer ---
open