Efficient indexing for shortest paths on DAGs

摘要: We propose an efficient algorithm which reports the length of a shortest path between any two nodes directed graph in constant time. Our indexing technique is extension labeling method for fast reach- ability test on DAGs, called R2HOP. In usual method, we can obtain time response query this problem by using adjacent matrix graph. However, requires huge memory space and it difficult to apply lage database. So introduce more practical problem, implement it, evaluated efficency preprocessing time/space size index experiments.