Given a graph $G(V,E)$ where every edge $e\in E$ has some positive weight $c(e)$. The graph can be directed/undirected/mixed. The graph is assumed to be strongly connected. Moreover, we define a subset of vertices $V'\subset V$. Let $P_{u,v}$ be the edges on the least cost path from $u$ to $v$, and $EP=\cup_{u\in V',v\in V'}P_{u,v}$.

Problem: find all edges in the set $E\setminus EP$.

In plain English: find all-pairs least cost paths between the vertices in $V'$; find all edges in $G$ which are *not* used by any of these least cost paths.

Is there an efficient way to compute this subset of edges? One could run Floyd-Warshall on graph G which runs in $O(V^3)$, but this seems rather inefficient if $V'$ is significantly smaller than $V$. Moreover, after running Floyd-Warshall, one still needs to iterate over all $(u,v)$ paths to find the edges that are used. I'm not sure how to do this efficiently.

pathsfrom $u$ to $v$, i.e. if there is more than one least cost path from $u$ to $v$, all edges on all of them are included in $EP$. $\endgroup$ – Robert Israel Jul 18 '17 at 0:48