动态图与增量计算：增量最短路径、增量 PageRank、连通性维护 ACERS 解析

初始: A->B(1), B->C(1), A->C(5)
最短路 A->C = 2

更新: A->C 权重降为 1
只需局部修复 A/C 邻域，最短路变为 1

图有两个分量 G1, G2
新增边 x(G1)-y(G2)
连通性结构应快速反映 “分量合并”

from collections import defaultdict, deque
import heapq


class DynamicGraphEngine:
    def __init__(self):
        self.g = defaultdict(dict)    # g[u][v] = w
        self.pending = deque()        # update log

    def add_edge(self, u, v, w=1.0):
        self.pending.append(("add", u, v, w))

    def remove_edge(self, u, v):
        self.pending.append(("del", u, v, None))

    def flush_updates(self, budget=1000):
        """延迟更新：批量应用，受 budget 控制"""
        cnt = 0
        while self.pending and cnt < budget:
            op, u, v, w = self.pending.popleft()
            if op == "add":
                self.g[u][v] = w
            else:
                self.g[u].pop(v, None)
            cnt += 1

    def shortest_path_local(self, s, t, max_hops=8):
        """局部重算示例：限制扩展深度/状态规模"""
        pq = [(0.0, 0, s)]  # dist, hops, node
        dist = {s: 0.0}
        while pq:
            d, h, u = heapq.heappop(pq)
            if u == t:
                return d
            if h >= max_hops:
                continue
            if d != dist.get(u):
                continue
            for v, w in self.g[u].items():
                nd = d + w
                if nd < dist.get(v, float("inf")):
                    dist[v] = nd
                    heapq.heappush(pq, (nd, h + 1, v))
        return float("inf")


if __name__ == "__main__":
    eng = DynamicGraphEngine()
    eng.add_edge("A", "B", 1)
    eng.add_edge("B", "C", 1)
    eng.add_edge("A", "C", 5)
    eng.flush_updates()
    print(eng.shortest_path_local("A", "C"))  # 2

    eng.add_edge("A", "C", 1)
    eng.flush_updates()
    print(eng.shortest_path_local("A", "C"))  # 1

// 伪代码：查询时只在 maxDepth 内做双向 BFS
// 在线返回近似最短跳数，异步任务补全精确路径

# 核心思想：对更新节点注入 residual，再局部 push 直到阈值 epsilon
# residual < epsilon 时停止传播

class DSU {
  constructor(n) { this.p = Array.from({length:n}, (_,i)=>i); }
  find(x){ return this.p[x]===x?x:(this.p[x]=this.find(this.p[x])); }
  union(a,b){ this.p[this.find(a)] = this.find(b); }
  connected(a,b){ return this.find(a)===this.find(b); }
}

# incremental shortest path (bounded local recompute) - simplified
import heapq

def local_dijkstra(graph, s, t, max_nodes=1000):
    pq = [(0, s)]
    dist = {s: 0}
    seen = 0
    while pq and seen < max_nodes:
        d, u = heapq.heappop(pq)
        if d != dist.get(u):
            continue
        seen += 1
        if u == t:
            return d
        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, 10**18):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return float("inf")

/* union-find for dynamic connectivity (insert-only fast path) */
#include <stdio.h>

int p[1000];
int find(int x){ return p[x]==x?x:(p[x]=find(p[x])); }
void uni(int a,int b){ p[find(a)] = find(b); }

int main(){
    for(int i=0;i<10;i++) p[i]=i;
    uni(1,2); uni(2,3);
    printf("%d\n", find(1)==find(3)); // 1
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p;
    DSU(int n): p(n) { iota(p.begin(), p.end(), 0); }
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    void unite(int a,int b){ p[find(a)] = find(b); }
    bool conn(int a,int b){ return find(a)==find(b); }
};

int main(){
    DSU d(6);
    d.unite(0,1); d.unite(1,2);
    cout << d.conn(0,2) << "\n"; // 1
}

package main

import "fmt"

type DSU struct{ p []int }
func NewDSU(n int) *DSU { d:=&DSU{make([]int,n)}; for i:=0;i<n;i++{d.p[i]=i}; return d }
func (d *DSU) Find(x int) int { if d.p[x]!=x { d.p[x]=d.Find(d.p[x]) }; return d.p[x] }
func (d *DSU) Union(a,b int){ d.p[d.Find(a)] = d.Find(b) }

func main(){
	d := NewDSU(6)
	d.Union(1,2); d.Union(2,3)
	fmt.Println(d.Find(1)==d.Find(3)) // true
}

struct DSU { p: Vec<usize> }
impl DSU {
    fn new(n: usize) -> Self { Self { p: (0..n).collect() } }
    fn find(&mut self, x: usize) -> usize {
        if self.p[x] != x { let r = self.find(self.p[x]); self.p[x] = r; }
        self.p[x]
    }
    fn union(&mut self, a: usize, b: usize) {
        let ra = self.find(a);
        let rb = self.find(b);
        self.p[ra] = rb;
    }
}

fn main() {
    let mut d = DSU::new(5);
    d.union(0, 1);
    d.union(1, 2);
    println!("{}", d.find(0) == d.find(2));
}

// lazy update queue skeleton
const pending = [];

function addEdge(u, v, w) {
  pending.push({ op: "add", u, v, w });
}

function flush(graph, budget = 100) {
  let cnt = 0;
  while (pending.length && cnt < budget) {
    const e = pending.shift();
    if (e.op === "add") {
      if (!graph.has(e.u)) graph.set(e.u, []);
      graph.get(e.u).push([e.v, e.w]);
    }
    cnt += 1;
  }
}