[Solved]: Shortest path from that passes through a set of edges once

Problem Detail: 

Given a graph with weighted edges. How to find the shortest path from vertex $A$ to vertex $B$ that passes through a set of edges $X$ at most once? $X$ can be big.

Slow solution: Finding shortest path from $A$ to each edge of $X$ and shortest path from each edge to $B$ in graph $G\setminus{X}$. Combining those paths and choosing the shortest one.

Can anyone think of a faster solution that doesn't require running Dijkstra's algorithm for each edge from $X$?

Asked By : Draex_

Answered By : Raphael

Assumption: Since you talk about Dijkstra, I assume you have non-negative edge weights.

Remember that Dijkstra already computes shortest paths to all other nodes. That is, after two runs -- one with $A$ and one with $B$ as starting node¹ -- you have shortest paths from $A$ to all nodes incident to $X$, and from $B$ to all nodes incident to $X$.

We just have to make sure that there are no edges from $X$ on these paths. The idea is to make edges from $X$ so expensive that choosing all other edges is better than picking just one edge from $X$. That actually pretty straight-forward to do.

Let $W = 1 + \sum_{e \in E} w(e)$; then modify the weights so that

$\qquad\displaystyle w'(e) = \begin{cases} w(e), &e \not\in X;\\W + w(e), &e \in X.\end{cases}$

A shortest path w.r.t. $w'$ of weight $<W$ is shortest w.r.t. $w$ when ignoring paths that hit $X$; if it has larger weight there is no path that avoids $X$ between the two nodes.

Now, if the shortest path from $A$ to $B$ you find by the two Dijkstra runs has weight $<W$, it is one contender for the shortest path. In addition, you have to find the best pair of paths that connect $A$ and $B$ to different ends of an $X$-edge. Combine for all $e \in X$ the shortest paths to $A$ and $B$, and add the original weight $w(e)$.

Note that there are two pairs of paths for each such $e$! That is, we get $2|X|+1$ paths to chose to minimal one from². So that is an additional $\Theta(|X|)$ effort, which is dominated by the initial runs of Dijkstra.

In total, this solves your problem with two Dikjstra runs and one graph modification that can be performed in $\Theta(|E|)$, or even on-the-fly if your algorithm is implemented with nice abstractions.

---

1. This only works in undirected graphs. If your edges are directed, you need to perform the second run on an reversed copy of $G$.
2. If there is none with weight $<W$ then the original graph doesn't have any path from $A$ to $B$ that hits $X$ at most once!

---

This answer saw heavy revision. While the ideas were all there from the start they were presented as two solutions, neither of which worked on its own. Credits to Draex_ for picking the post apart!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57792

 Ask a Question

 Download Related Notes/Documents