# Mininun changes required in a directed graph to make path from 1 to n

i have a directed graph. Basically, i have to find how many edges i need to change to opposite direction to make a path between 1 and n. So, i tried solving it by making the graph undirected and marking the directions as -1 or +1 and then going through all paths and finding which paths has minimum -1(s). I store graph data in adjacency list (because number of edges can be large) and perform dfs. I also stop travelling a path if its count of -1(s) is more than the previous minimum. I also stored in every element the previous count of -1(s) to reach it from start. and i stop if current count is more. If less, i update it and move on this path and update if the new count is minimum. But this approach is slow. What else can i try?

• I think contests are designed to be solved on your own. – Raphael Aug 8 '14 at 9:30

## 1 Answer

Construct a weighted directed graph as follows. For each edge (u,v), there are an edge (u,v) of weight 0 and an edge (v,u) of weight one. Then, there is an path from 1 to n of weight k iff we can change direction of k edges to make a path. Thus, the problem can be solved by a shortest path algorithm. Since the edge weights are either 0 or 1, it can also be solved by BFS.