2
$\begingroup$

Given a undirected graph $G=(V,E)$.

Imagine traversing the Graph was restricted; following an edge $a$ over a node $v$ to an edge $b$ is allowed if and only if a function $w: ( a, v, b ) \rightarrow \{0,1\}$ returns $1$.

Is there a effective solution to find the shortest path between two nodes without trying every possible path on the graph? (Since without visiting every node from every possible direction it is not guaranteed to follow every edge that might exist. Also, just remembering if a node has been already visited nor not does not fit anymore since there might be other leaving edges allowed to take - depending on the incoming edge that had been taken. )

Also, is there a more common formulation of this problem (e.g. “restricted traversal”) ?

$\endgroup$
  • $\begingroup$ If there are 2 edges a{x, v} and b{v, y} sharing a node v and (a, v, b) = 1 then a new graph can be created in which there will be an edge {x,y}. Now normal shortest path algo can be executed on this new graph. $\endgroup$ – sameerkn Feb 24 '17 at 8:49
  • $\begingroup$ cs.stackexchange.com/q/118977/755 $\endgroup$ – D.W. Jan 19 at 19:31
2
$\begingroup$

Yes, here's an algorithm for that. Construct a new graph $G' = (V\times V, E')$ where you have an edge $(u,v) \to (v,w)$ for each triple of vertices $u,v,w \in V$ such that $(u,v) \in E$, $(v,w) \in E$, and $w((u,v),v,(v,w))=1$. Now look for the shortest path in $G'$. This graph basically keeps track of the current node and the previous node; the node $(u,v)$ in $G'$ corresponds to a traversal in $G$ where the current node is $v$ and the previous node was $u$.

If you know finite automata, this is basically a product construction (parallel composition).

| cite | improve this answer | |
$\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.