Решаем для каждой веришины и всех ее искходящих ребер. Делаем обход в ширину по прямым ребрам из этой вершины, для каждой доступной вершины запоминаем через какое ребро мы прошли, разбиваем по такому принципу весь граф на компоненты. Заметим, что кратчайший обходной путь для i-ой вершиныкогда нибудь в последний раз воткнется в i-ую компоненту а потом будет идти внутри этой компоненты. Таким образом для каждой вершины i-ой компоненты найдем длину кратчайшего пути до вершины i (это можно сделать запустив обход в ширину по обратным ребрам для всех вершин до которых идут ребра из первоначальной вершины) и минимальное расстояние до вершины не из i-ой компоненты из которой есть ребро в данную, и найдем минимум по d_1 + d_2 + 1