# Recent Advances in Efficient Dynamic Graph Processing
## 4 Algorithms
### Path Traversal
#### 4.4.2 Shortest Distance Queries
While [107; 108]'s Dijkstra-based algorithms can efficiently solve shortest distance queries, high computational cost incurs when the graph is large. Consequently, significant research has focused on developing efficient indexing techniques for shortest-path queries. [PERSON]. [105] introduces two dynamic indexing structures for shortest-path and distance queries on large time-evolving graphs, which represent the first practical exact solutions capable of simultaneously handling both real-time distance queries and graph updates in evolving networks. And then, Ref. [105] proposes a dynamic indexing scheme, namely dynamic pruned landmark labeling, for queries on the last snapshot. While the indexing framework in [105] lacks support for edge deletions, this operation frequently occurs in practical scenarios such as social network analysis, where user relationships dissolve. To address this limitation, the work in [109] develops specialized algorithms for computing the shortest path distance, particularly under decremental updates. They propose maintenance algorithms based on 2-hop cover, which can handle decremental updates efficiently. Similarly, the work in [100] develops a general approach for answering distance queries in fully dynamic graphs. Specifically, they propose a novel dynamic algorithm to update 2-hop cover labels during edge deletions, ensuring the minimality of the labels--an important feature that influences both storage requirements and query performance. The aforementioned algorithms for processing shortest-distance queries on dynamic graphs are primarily designed for in-memory computation, limiting their applicability to large-scale graphs. To address this issue, several external-memory algorithms have been developed. For instance, the work in [106] investigates exact shortest-distance queries on disk-resident scale-free dynamic graphs and introduces two I/O-efficient algorithms for updating canonical labeling--a specialized form of 2-hop distance labeling. Meanwhile, the study in [104] concentrates on the incremental maintenance of all-pairs shortest distances. Their algorithms utilize general operators that can be adapted across various database management systems (DBMSs), making them compatible with both in-memory and disk-based DBMS implementations. Ref. [103] presents a deterministic data structure for incremental SSSP in weighted directed graphs with total update time \(\hat{O}(n^{2}\log\frac{w}{e^{\hat{O}(1)}})\) which is near-optimal for very dense graphs. Here, \(w\) is the ratio of the largest weight in the graph to the smallest, and \(n\) is the number of vertices in the graph. Ref. [101] investigates the \(k\)-shortest paths in a dynamic road network and proposes a distributed algorithm for finding \(k\)-shortest paths in a dynamic graph. Current studies that employ hub labeling techniques for real-time shortest path counting are limited by their dependence on a pre-computed index, which cannot tackle frequent updates over dynamic graphs. To address this, Ref. [102] proposes a novel approach for maintaining the index in response to change in the graph structure and develops incremental and decremental update algorithms for inserting and deleting vertices/edges, respectively. The main idea of these two algorithms is to update only the affected vertices, significantly reducing the time cost. Both [105; 105] study the maintenance of SD-Index, but the pruning conditions of [105] are insufficient. In addition, the method in [105] only records the shortest distance in the BFS process, not the number of shortest paths. [PERSON]. [99] studies the exact fully dynamic shortest paths problem. It gives a MonteCarlo randomized fully dynamic reachability data structure processing single-edge updates in \(\hat{O}(n\sqrt{m})\) worst-case time and queries in \(O(\sqrt{m})\) time. **Algorithm analysis. ** Many existing dynamic shortest path algorithms rely on index-based structures to efficiently maintain and update shortest path information as the graph changes.