# Recent Advances in Efficient Dynamic Graph Processing
## 4 Algorithms
### Path Traversal
#### 4.4.2 Shortest Distance Queries  
Given a graph \(G\), a shortest distance query asks the minimized length of all the paths between two query vertices in \(G\). Without doubt, answering shortest distance queries is one of the most fundamental operations on graphs. It is a primitive as either a main function or a building block of applications including geographic navigation, internet routing, socially tenuous group finding [159], influential community searching [160], and event detection [161]. A straightforward approach to answering shortest distance queries is breadth-first search on unweighted graphs or [PERSON]'s algorithm on positively weighted graphs. However, this approach may traverse the entire graph when two query vertices are far apart, and thus it incurs high computational cost especially when the graph is large. Consequently, indexing methods for efficiently answering shortest distance queries have been intensely studied [162; 163]. Considering that real-world networks are highly dynamic, operations of users are bursty in regard to temporal locality [105]; it is tricky to design efficient index maintenance algorithms without reconstructing indices from scratch. Ref. [107] studies the dynamic shortest path problem, which aims to recompute shortest path trees (SPTs) with a set of edge weight updates on a dynamic graph \(G\). In order to handle multiple edge weight updates, the authors of [107] propose several dynamic SPT algorithms, namely DynDijkstra, MBall-StringInc and MFP, which extend and correct several existing dynamic SPT algorithms [164; 132]. To be specific, MBall-StringInc [107] is proposed to amend BallString [164], which cannot update SPTs correctly in the case of multiple edge weight increase. MFP [107] is proposed to tackle the inefficiency problem of DynamicSWSF-FP [132], and it supports fully dynamic edge weight updates (i.e., with both edge weight increases and decreases). DynDijkstra [107] is a simple dynamic version of Dijkstra, which includes the algorithms of DynDijkstraInc and DynDijkstraDec that are designed to handle multiple edge weight increases and decreases, respectively. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Problem** & **Algorithm** & **Graph Type** & \begin{tabular}{c} **Update** \\ **Mode** \\ \end{tabular} & **Fully Dynamic** & \begin{tabular}{c} **Incremental** \\ **Dynamic** \\ \end{tabular} & \
\begin{tabular}{c} **Decmental** \\ **Dynamic** \\ \end{tabular} &
\begin{tabular}{c} **Streaming** \\ **Dynamic** \\ \end{tabular} \\ \hline DFS-Tree & Franciosa [95] & DAG & Batch & ✗ & \(O(n)\) & ✗ & ✗ \\ DFS-Tree & Baswana [96] & General & Batch & ✗ & \(O(n^{2}/m)\) & ✗ & ✗ \\ DFS-Tree & Baswana [98] & DAG & Batch & ✗ & \(O(n\log n)\) & ✗ \\ DFS-Tree & Baswana [94] & General & Batch & \(O(\sqrt{mn}\log^{2.5}n)\) & \(O(n^{3}n)\) & ✓ & ✗ \\ DFS-Tree & Chen [91] & General & Batch & \(O(\sqrt{mn}\log^{1.5}n)\) & \(O(n)\) & ✓ & ✗ \\ DFS-Tree & Nakamura [92]-A \({}^{1}\) & General & Batch & \(O(\sqrt{mn}\log^{1.5+}n)\) & \(O(n\sqrt{\log n})\) & ✓ & ✗ \\ DFS-Tree & Nakamura [92]-B \({}^{1}\) & General & Batch & \(O(\sqrt{mn}\log^{1.25}n)\) & \(O(n\log n)\) & ✓ & ✗ \\ DFS-Tree & Baswana [93] & General & Batch & \(O(\sqrt{mn}\log n)\) & ✓ & ✓ & ✗ \\ \hline \hline \end{tabular}  
\({}^{1}\) [PERSON] [92] proposes two algorithms Nakamura-A and Nakamura-B.  
\end{table} 
Table 7: Comparison of time complexity for dynamic DFS-Tree algorithms. Ref. [108] investigates dynamic single-source shortest path (SSSP) computation, and introduces two algorithms: LazyDijkDec for edge weight decreases and LazyDijkInc for increases. LazyDijkDec optimizes DynDijkstraDec [107] by terminating SPT computation upon finding the target path. LazyDijkInc reformulates DynDijkstraInc [107] into a set of edge weight decreases in an altered graph enabling LazyDijkDec to handle subsequent updates without intermediate SPT computation. Experimental results indicate these methods offer only marginal improvements over [107]'s original approaches.