Minimum Flip Connectivity Problem
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$.