Проблема: учитывая взвешенный направленный ациклический граф (DAG) и исходную вершину s в нем, найдите наибольшие расстояния от s до всех других вершин в данном графе.
Найдите справочную диаграмму: ссылка
Зачем нужна топологическая сортировка? Разве мы не можем просто использовать модифицированный BFS из исходной вершины. Почему нам так важен линейный порядок?
Если это повторение, то любезно перенаправьте меня на соответствующие ответы.
Спасибо
Если мы не сортируем его, мы не знаем, какую соседнюю вершину выбрать в первую очередь, и это может привести к ситуации, когда мы используем расстояние вершины v для обновления расстояний до ее соседних вершин adj[v], но после этого расстояние вершина v обновляется, поэтому вершины из adj[v] также могут иметь большие расстояния, но мы больше не будем их посещать.
Пример, основанный на указанном вами графике (http://www.geeksforgeeks.org/wp-content/uploads/LongestPath.png):
Предположим, что на этом этапе: 
Скажем, мы начинаем обход графа с вершины '0' и выбираем вершину с расстоянием 6 (вместо вершины с расстоянием 2, которое мы бы выбрали, если бы использовали топологический порядок ). Уже обработанные вершины имеют зеленый цвет, вершина, обрабатываемая в данный момент, - красная: 
Мы обновили расстояние от последней вершины до 7, и мы не будем увеличивать его, однако, если бы мы посетили вершину с расстоянием 2 на предыдущем шаге, расстояние до этой вершины было бы 10: 
Если мы сможем отслеживать посещенные узлы, должно быть возможно использовать рекурсивную DFS и некоторую мемоизацию.
Начать с начального узла. Для каждого соседа рассчитайте (расстояние до соседа + расстояние от соседа до цели). Возьмите максимум из них, запомните его как максимум из этого узла и верните его.
По сути, если вы знаете максимальное расстояние от ваших соседей до цели, вы знаете максимальное расстояние от вас до цели. И если вы запомните, вы не посетите какой-либо узел более одного раза.
Если вы знаете, как это сделать с "модифицированной BFS", то можете и так. Как вы предлагаете сделать это с "модифицированной BFS", кстати?
Между тем, алгоритм, представленный по ссылке, сначала выполняет сортировку графа. Вот как устроен этот алгоритм.
Теперь заказ топосорта создается алгоритмом DFS на этапе обратного отслеживания. К сожалению, DFS формирует порядок топосортировки в обратном направлении. По этой причине мы не можем «встроить» конкретную обработку алгоритма самого длинного пути непосредственно в DFS. (Этот алгоритм требует обработки в направлении вперед.) Следовательно, мы должны принять двухпроходный подход: сначала выполнить чистую DFS, чтобы построить полную топосортированную последовательность, а затем сделать второй проход, чтобы найти самый длинный путь .
Во многих реальных ситуациях полезны алгоритмы, основанные на топосорте, потому что вершины DAG могут быть уже сохранены в порядке топосорта. Т.е. топосортировка выполняется только один раз на этапе предварительной обработки. После этого различные алгоритмы на основе топосорта фактически превращаются в очень эффективные однопроходные алгоритмы без дополнительных требований к памяти (в отличие от таких алгоритмов, как BFS или DFS, которые требуют дополнительной памяти для своих стеков, очередей и т. Д.)
Топологическая сортировка не требуется, если вы жадно обрабатываете узлы каждый раз, когда происходит обновление. Если вы с жадностью пересмотрите всех соседей, то сможете улучшить самые длинные дистанции. Например, на этапе 9 вы можете просто проверить, что 9 + 1> 7, и повторно посетить 7-й узел, чтобы обновить его.
