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?
Mininun changes required in a directed graph to make path from 1 to n
algorithms;graph theory;dynamic programming;graph algorithms