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.



Find all edges not covered by a shortest path in an all-pairs shortest path over a subset of vertices
I'll assume for simplicity the graph is undirected.


Run Dijkstra $|V'|$ times to find the distance $D(v,w)$ from each vertex $v$ of $V'$ to each vertex $w$ of $V$. Then an edge $E = (a,b)$ is in $EP$ if and only if there exist
$u,v \in V'$ such that $D(u,v) = D(u,a) + D(v,b) + c(a,b)$. 


