1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Robert Israel Jul 18 '17 at 0:48
  • $\begingroup$ 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) $\endgroup$ – Joris Kinable Sep 18 '17 at 9:35
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I currently use the following approach: For each vertex v of V', I use Dijkstra to compute a Shortest Path Tree T rooted in v. Then EP is the union of all the edges in those trees. The resulting runtime complexity is O(|V'||E|+|V'||V|log |V|). On a graph with |V|=16k and |E|=27k this takes about a minute on a desktop computer. $\endgroup$ – Joris Kinable Sep 18 '17 at 9:50
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.