Problem: for a given graph, print the shortest path from one vertex to another. In 626, a cycle with 3 vertices is requested.
Size: 300 nodes at most.
Solution: either BFS or all-pair shortest path do the job. With a graph with N nodes and edges stored in list, BFS takes O(N) for each query. All-pair shortest path takes O(N^3) preprocess, thus much more inefficient.
Note: it is not specified, but all nodes are labeled with id from 1 to N. Furthermore, there exists no query from a vertex to itself. This makes codes compact.
No comments:
Post a Comment