Sum of all pairs' shortest path
Difference between en1 and en2, changed 10 character(s)
You are given an weighted undirected graph consisting of n vertices and m edges ($1 \leq n, m \leq 10^5$). Let $d(u, v)$ be the shortest distance between $u$ and $v$. What is the best algorithm to calculate $\sum_{1 \leq u < v \leq n} d(u, v)$?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Minh639 2024-05-13 15:03:48 10 Tiny change: 're given an undirecte' -> 're given a weighted undirecte'
en1 English Minh639 2024-05-13 13:32:35 266 Initial revision (published)