Dynamic Graphs: SSSP

Chapter 2: Single-Source Shortest Path (SSSP) on Dynamic Graphs

Introduction

Finding the shortest path between a source node and all other nodes in a graph is a well-studied problem in computer science. Algorithms like Dijkstra's and Bellman-Ford are commonly used for static graphs. In this chapter, we'll explore the intricacies of applying SSSP algorithms to dynamic graphs where vertices and edges can be added or removed over time.

Standard SSSP Algorithms

A quick refresher on some popular SSSP algorithms for static graphs:

1. Dijkstra's Algorithm: Works for graphs with non-negative weights. It uses a priority queue to explore the graph.
2. Bellman-Ford Algorithm: Works even for graphs with negative weights (but without negative-weight cycles). It relaxes edges repeatedly.

Dijkstra's Algorithm

  Dijkstra(Graph G, Node s):
    1. Initialize distance array dist[] with infinities
    2. Set dist[s] = 0
    3. Initialize priority queue Q and insert (s, 0)
    4. while Q is not empty:
        5. u = Q.extract_min()
        6. for each neighbor v of u:
            7. if dist[v] > dist[u] + weight(u, v):
                8. Update dist[v]
                9. Q.insert_or_update(v, dist[v])

Dynamic Graphs and SSSP

A dynamic graph \( G_t = (V_t, E_t) \) at time \( t \) can change over time. The primary challenges for dynamic SSSP are:

• When vertices or edges are added, new shortest paths may emerge.
• When vertices or edges are removed, existing shortest paths may become invalid.

SSSP on Dynamic Graphs

Strategies to adapt SSSP algorithms for dynamic graphs:

1. Recomputing from Scratch: Simple but costly, especially for large graphs.
2. Incremental Updates: Update the shortest paths incrementally to save computational time.

Incremental SSSP Algorithm

  IncrementalSSSP(Graph G_t, Node s, dist[]):
    1. Detect changes (added/removed vertices and edges)
    2. Update dist[] according to the changes
    3. Correct any inconsistencies in dist[] (e.g., recompute paths if needed)

Conclusion

Just like BFS, Single-Source Shortest Path algorithms can be adapted for dynamic graphs. The key is to efficiently update the shortest paths as the graph changes over time.