Minimum Flip Connectivity Problem I formulated the following problem today while playing with my GPS. Here it is :

Let $G(V,E)$ be a directed graph such that if $e=(u,v) \in E$ then $(v,u) \notin E$, i.e., $G$ is an orientation of the underlying undirected graph. Consider the following operations :


$Flip(u,v)$ : Replace an edge $(u,v)$ with an edge $(v,u)$
$undirect(u,v)$ : Make the edge $(u,v)$ undirected


Let $s,t \in V$ be two special vertices. Consider the following optimization problems :


Min-Flip st-connectivity : Given $G$ and two vertices $s,t$ find the minimum number of edges that need to be flipped to make a directed path from $s$ to $t$.
Min-Flip strong-connectivity : Given $G$ find the minimum number of edges that need to be flipped to make $G$ strongly connected. If it is not possible to make $G$ strongly connected by flipping edges then output NO.
Min-undirect strong-connectivity : Given $G$ find the minimum number of edges that need to be undirected to make $G$ strongly connected.


Note that you are not allowed to add "new" edges. You are only modifying the existing edges using the above operations. Is this problem known in the literature. If so what are the known results ?
This is an answer for the first problem:
Consider a new weighted graph $G&#39;=(V,E&#39;)$, where $E&#39;=\{(u,v,0)|(u,v) \in E\} \cup \{(v,u,1)|(u,v)\in E \}$ (weights of all edges that are in $G$ are 0, and weights of 'reversed' edges are 1). Now You just have to find the shortest path from $s$ to $t$.