Single-Source Shortest Paths
- PDF / 220,699 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 68 Downloads / 265 Views
in a directed graph subject to an intermixed sequence of edge insertions and edge deletions. The bounds reported in this entry were originally presented for the case of directed acyclic graphs, but can be extended to general directed graphs using the following theorem from [2]: Theorem 1 Given a general directed graph with n vertices, there is a data structure for the fully dynamic reachability problem that supports each insertion/deletion in O(n1:575 ) time and each reachability query in O(n0:575 ) time. The algorithm is randomized with one-sided error. The idea described in [1] is to maintain reachability information from the source vertex s to all other vertices explicitly by keeping a Boolean array R of size n such that R[y] = 1 if and only if there is a directed path from s to y. An instance D of the data structure for fully dynamic reachability of Theorem is also maintained. After each insertion or deletion, it is possible to update D in O(n1:575 ) time and then rebuild R in O(n n0:575 ) = O(n1:575 ) time by letting R[y] D:reachable (s,y) for each vertex y. This yields the following bounds for the single-source fully dynamic reachability problem: Theorem 2 Given a general directed graph with n vertices, there is a data structure for the single-source fully dynamic reachability problem that supports each insertion/deletion in O(n1:575 ) time and each reachability query in O(1) time. Applications The graph reachability problem is particularly relevant to the field of databases for supporting transitivity queries on dynamic graphs of relations [3]. The problem also arises in many other areas such as compilers, interactive verification systems, garbage collection, and industrial robotics. Open Problems An important open problem is whether one can extend the result described in this entry to maintain fully dynamic single-source shortest paths in subquadratic time per operation. Cross References Trade-Offs for Dynamic Graph Problems Recommended Reading 1. Demetrescu, C., Italiano, G.: Trade-offs for fully dynamic reachability on dags: Breaking through the O(n2 ) barrier. J. Assoc. Comput. Machin. (JACM) 52, 147–156 (2005)
S
2. Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse. In: FOCS ’04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS’04), pp. 509– 517. IEEE Computer Society, Washington DC (2004) 3. Yannakakis, M.: Graph-theoretic methods in database theory. In: Proc. 9-th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Nashville, 1990 pp. 230–242
Single-Source Shortest Paths 1999; Thorup SETH PETTIE Department of Computer Science, University of Michigan, Ann Arbor, MI, USA
Keywords and Synonyms Shortest route; Quickest route
Problem Definition The single source shortest path problem (SSSP) is, given a graph G = (V ; E; `) and a source vertex s 2 V , to find the shortest path from s to every v 2 V. The difficulty of the problem depends on whether the graph is directed or undirected and the assumptions placed on the length function
Data Loading...
