Shortest path in Directed Acyclic Graph with small degree
Given a weighted directed acyclic graph on n vertices such that each vertex has indegree at most 5 and outdegree at most 5 . The nodes 0, 1, ..., n - 1 are oriented like this
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
...
n-5 n-4 n-3 n-2 n-1
Edges can only be from a node in a row to some node in the next row.
We'll be given q queries, asking the shortest path length from u to v . Here n can be upto 10^5 and q upto 10^4 . Weights are all positive integers.
Can we do better than O(nq) dynamic programming (which clearly doesn't work here)?
This seems too good to be true, sorry if it's not... You can get O(n) (EDIT: O(n^(4/3)) ) preprocessing and O(1) query.
I'm considering that you know how to compute all the shortest distances between all the nodes in the graph in time O(n^2) . (which is indeed possible, you seem to know that)
Divide your graph in k blocks, each containing n/(5*k) rows. (the blocks should start and finish on complete rows, and two consecutive ones overlap on their respective first and last row)
Compute the shortest path between all nodes (and in particular the first and last row) in each block: O((n/k)^2) .
Then you can consider the reduced graph containing only the nodes at the boundary between two blocks, with edges value equal to the shortest path between them that you've just computed.This reduced graph is of size O(k) . Compute all the shortest paths in that graph in time O(k^2) .
Total preprocessing time: O((n/k)^2 + k^2) . Take k=sqrt(n) , you get O(n) preprocessing.
The query time is then O(1) : take the 5 nodes at the end of u's block, the 5 at the start of v's block (if the blocks are different), you just need to compare the 25 possibilities for u->v
EDIT
Of course it's false. You actually have k blocks for which to compute the shortest paths, so the total complexity for that step is O(k*(n/k)^2) . so the total is O(n^2/k + k^2) , and the best choice for k is k=n^(2/3) , which gives a total complexity of preprocessing of O(n^(4/3)) and total queries O(q)
上一篇: 肥皂ui生成的代码
下一篇: 定向非循环图中的最短路径具有小的程度