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$?

  • $\begingroup$ That's much better! Now you mention vertices $A$ and $B$ and you show the kind of solution you're (not) looking for. Is there a reason your algorithm doesn't compute the shortest path from $A$ to $B$ without restrictions? After all, a solution that passes through no edge in $X$ is also admissible. $\endgroup$ May 24 '16 at 10:48
  • $\begingroup$ @LieuweVinkhuijzen Yes, an extra pass with Dijkstra's algorithm through $G\setminus{X}$ is necessary. $\endgroup$
    – Draex_
    May 25 '16 at 6:11

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!


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.