number of edges that appeared at least in one shortest path

Question

In a simple weighted graph, with n vertices and m edges , for each pair of vertices we want to find the number of edges that appeared at least in one of the shortest paths between these two vertices.

I assume we can solve it using Floyd-Warshall algorithm or something similar to it but I tried and didn't reach any algorithm. I think its complexity should be O(N^3)

Answer 1

The following is a naive algorithm:

1. Run Floyd-Warshall algorithm. It will give the shortest path values $d(s,t)$ between every pair of vertices $s, t \in V$.
2. For each edge $(u,v)$ and pair of vertices $s$ and $t$, if $d(s,u) + d(u,v) + d(v,t)= d(s,t)$, means there exists a shortest path from $s$ to $t$ via edge $(u,v)$.

In this way, you can compute the number of edges that appeared in at least in one of the shortest paths between any two vertices. The running time of the step $1$, is $O(|V|^3)$ and step $2$ is $O(|E| \cdot |V|^2)$. Therefore, the overall running time is $O((|E|+|V|) \cdot |V|^2)$.