Naive
All-pairs shortest paths, count. O(V³) with Floyd-Warshall + O(V²) counters.
Advertisement
Brandes' algorithm
Single-source dependency accumulation. For each source: BFS (unweighted) or Dijkstra (weighted), then aggregate. O(VE) unweighted, O(VE + V² log V) weighted.
Advertisement
Applications
Identify bottleneck nodes in networks. Social network 'connector' identification. Robustness analysis.
Approximation
Sample sources. Riondato-Kornaropoulos: (ε, δ)-approximation in O(1/ε² · log(1/δ)) source samples.