# Restricted traversal on an undirected graph

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”) ?

• 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. – sameerkn Feb 24 '17 at 8:49
• cs.stackexchange.com/q/118977/755 – D.W. Jan 19 at 19:31

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