# number of edges that appeared at least in one shortest path

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)

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)$$.