#algorithm #graph #directed-acyclic-graphs #longest-path
#алгоритм #График #направленные ациклические графы #самый длинный путь
Вопрос:
Есть ли эффективный способ удалить все ребра, которые не являются частью самых длинных путей между двумя узлами в DAG? Например, для графика (DAG): (1->2, 2->3, 2->4, 1->3, 1->4) Я хочу удалить ребра 1-> 3, 1-> 4, так как пути 1-> 2->3, 1-> 2-> 4 длиннее
Редактировать: итак, я думаю, что лучший способ — использовать топологическую сортировку и перемещаться по массиву справа налево, агрегируя для каждого узла его потомков. Затем для каждого ребра a-> b мы можем проверить, достижимо ли b из a, используя все другие прямые потомки a (и если это так, мы удаляем ребро). Но я не нашел реализации, и я не уверен, что это правильно, кто-нибудь знает о реализации чего-то подобного?
Комментарии:
1. Как насчет удаления всех ребер, а затем добавления ребер, которые являются частью самого длинного пути. (зависит от вашей фактической реализации)
Ответ №1:
Алгоритм, который вы предлагаете, верен, потому что если ребро находится на любом самом длинном пути, то это должен быть самый длинный и единственный путь от его источника до целевых вершин. Таким образом, вы можете удалить любое избыточное ребро.
Название того, что вы пытаетесь сделать, — «транзитивное сокращение»: https://en.wikipedia.org/wiki/Transitive_reduction
Хотя ваш алгоритм работает, я не вижу, чтобы топологическая сортировка приносила вам какую-либо пользу. Простой алгоритм состоит в том, чтобы выполнить поиск из каждой вершины, чтобы найти другие способы достижения соседних вершин.