# Find all edges not covered by a shortest path in an all-pairs shortest path over a subset of vertices

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.

• By "the least cost path from $u$ to $v$", presumably you mean "the least cost paths from $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$. – Robert Israel Jul 18 '17 at 0:48
• If the least cost path is not unique (i.e. there's more than 1), then choose one arbitrarily. This problem has applications in vehicle routing over road networks. The graph representing all the roads is huge, but most streets are irrelevant for routing purposes (e.g. small residential streets) – Joris Kinable Sep 18 '17 at 9:35

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)$.
Note that you can run the Floyd-Warshall algorithm in $O(|V|^2\,|V'|)$ time to obtain shortest paths from $V'$ to everything. You need a $|V|\times |V'|$ matrix instead of a $|V|\times |V|$ matrix. It won't be theoretically faster than Robert's method but the constant will be very small so perhaps it is competitive in practice.