Shortest path from that passes through a set of edges once
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), &amp;e \not\in X;\\W + w(e), &amp;e \in X.\end{cases}$

A shortest path w.r.t. $w'$ of weight $&lt;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 $&lt;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.




This only works in undirected graphs. If your edges are directed, you need to perform the second run on an reversed copy of $G$.
If there is none with weight $&lt;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!