Найти самый длинный путь в списке смежности

Question

У меня есть список смежности, который я создал для данного графа с узлами и взвешенными ребрами. Я пытаюсь выяснить, как лучше всего найти самый длинный путь на графике. У меня есть метод топологической сортировки, который, как я слышал, может быть полезен, но я не уверен, как его реализовать, чтобы найти самый длинный путь. Так есть ли способ сделать это с помощью топологии сортировки или есть более эффективный метод?

Вот пример моего выхода из списка приставок (значение в скобках - это стоимость перехода в узел после стрелки (cost)to get to -> node:

Node 0 (4)->1(9)->2
Node 1 (10)->3
Node 2 (8)->3
Node 3
Node 4 (3)->8(3)->7
Node 5 (2)->8(4)->7(2)->0
Node 6 (2)->7(1)->0
Node 7 (5)->9(6)->1(4)->2
Node 8 (6)->9(5)->1
Node 9 (7)->3
Node 10 (12)->4(11)->5(1)->6

Answer 1

Брайан уже ответил на ваш вопрос выше, но я подумал, что могу углубиться.

Во-первых, как он указал, эта проблема легко разрешима только при отсутствии циклов. Если есть циклы, вы сталкиваетесь с ситуацией, когда у вас бесконечно длинные пути. В этом случае вы можете определить самый длинный путь, который будет любым путем без повторяющихся узлов. К сожалению, эта проблема может показаться NP-Hard. Поэтому вместо этого мы сосредоточимся на проблеме, которую, по-видимому, вам действительно нужно решить (поскольку вы упомянули топологическую сортировку)- самый длинный путь в направленном ациклическом графе (DAG). Мы также будем предполагать, что у нас есть два узла s а также t это наши начальный и конечный узлы. В противном случае проблема немного сложнее, если вы не можете сделать определенные предположения о вашем графике. Если вы понимаете текст ниже, и такие предположения на ваших графиках верны, то, возможно, вы можете удалить s а также t ограничения (в противном случае вам придется запускать его на каждой паре вершин в графе! Медленно...)

Первый шаг в алгоритме - это топологически упорядочить вершины. Интуитивно это имеет смысл. Допустим, вы заказываете их слева направо (то есть крайний левый узел не будет иметь входящих ребер). Самый длинный путь из s в t обычно начинается слева и заканчивается справа. Также невозможно, чтобы путь когда-либо шел в левом направлении. Это дает вам последовательный порядок для создания самого длинного пути - начните слева и двигайтесь вправо.

Следующим шагом будет последовательно идти слева направо и определить самый длинный путь для каждого узла. Для любого узла, у которого нет входящих ребер, самый длинный путь к этому узлу равен 0 (это верно по определению). Для любого узла с входящими ребрами, рекурсивно определите самый длинный путь к этому узлу, чтобы быть максимальным по всем входящим ребрам + самый длинный путь, чтобы добраться до "входящего" соседа (обратите внимание, что это число может быть отрицательным, если, например, все из входящих ребер отрицательны!). Интуитивно это имеет смысл, но доказательство также тривиально:

Предположим, наш алгоритм утверждает, что самый длинный путь к некоторому узлу v является d но самый длинный путь d' > d, Выберите "наименьший" такой узел v (мы используем порядок, определенный топологической сортировкой. Другими словами, мы выбираем "самый левый" узел, в котором наш алгоритм потерпел неудачу. Это важно, чтобы мы могли предположить, что наш алгоритм правильно определил самый длинный путь для любого узлы "слева" от v). Определите длину гипотетического самого длинного пути, который будет d' = d_1 + e где d_1 длина гипотетического пути до узла v_prev с краем e в v (обратите внимание на небрежное наименование. Край e также имеет вес e). Мы можем определить его как таковой, потому что любой путь к v должен пройти через одного из своих соседей, которые имеют преимущество v (так как вы не можете добраться до v не попасть туда через какой-то край, который идет к нему). затем d_1 должен быть самый длинный путь к v_prev (иначе, противоречие. Существует более длинный путь, который противоречит нашему выбору v как "наименьший" такой узел!) и наш алгоритм выберет путь, содержащий d_1 + e по желанию.

Для создания фактического пути вы можете выяснить, какое ребро было использовано. Скажем, вы восстановили путь до некоторой вершины v который имеет самую длинную длину пути d, Затем пройдитесь по всем входящим вершинам и найдите ту, которая имеет наибольшую длину пути d' = d - e где e вес ребра, входящего в v, Вы также можете просто отслеживать родительские узлы при прохождении алгоритма. То есть, когда вы найдете самый длинный путь к v, установите его родительский в зависимости от того, какой соседний узел был выбран. Вы можете использовать простое противоречие, чтобы показать, почему любой метод генерирует самый длинный путь.

Наконец, некоторый псевдокод (извините, это в основном на C#. Это намного сложнее, чем код на C без пользовательских классов, и я давно не кодировал C).

public List<Nodes> FindLongestPath(Graph graph, Node start, Node end)
{
    var longestPathLengths = Dictionary<Node, int>;

    var orderedNodes = graph.Nodes.TopologicallySort();
    // Remove any nodes that are topologically less than start. 
    // They cannot be in a path from start to end by definition
    while (orderedNodes.Pop() != start);
    // Push it back onto the top of the stack
    orderedNodes.Push(start);

    // Do algorithm until we process the end node
    while (1)
    {
        var node = orderedNodes.Pop();
        if (node.IncomingEdges.Count() == 0)
        {
            longestPathLengths.Add(node, 0);
        }
        else
        {
            var longestPathLength = Int.Min;
            foreach (var incomingEdge in node.IncomingEdges)
            {
                var currPathLength = longestPaths[incomingEdge.Parent] +               
                                     incomingEdge.Weight);
                if (currPathlength > longestPathLength)
                {
                    longestPath = currPathLength;
                }
            }

            longestPathLengths.Add(node, longestPath);
        }

        if (node == end)
        {
            break;
        }
    }

    // Reconstruct path. Go backwards until we hit start
    var node = end;
    var longestPath = new List<Node>();
    while (node != start)
    {
        foreach (var incomingEdge in node.IncomingEdges)
        {
            if (longestPathLengths[incomingEdge.Parent] == 
                    longestPathLengths[node] - incomingEdge.Weight)
            {
                longestPath.Prepend(incomingEdge.Parent);
                node = incomingEdge.Parent;
                break;
            }
        }
    }

    return longestPath;
}

Обратите внимание, что эта реализация не особенно эффективна, но, надеюсь, она понятна! Вы можете оптимизировать множество небольших способов, которые должны быть очевидны, если вы продумываете код / ​​реализацию. Как правило, если вы храните больше информации в памяти, она будет работать быстрее. То, как вы структурируете свои Graph тоже критично. Например, не похоже, что у вас IncomingEdges свойство для ваших узлов. Но без этого поиск входных ребер для каждого узла является трудной задачей (и не производительным!). На мой взгляд, алгоритмы графа концептуально отличаются, скажем, от алгоритмов для строк и массивов, потому что реализация так важна! Если вы прочитаете вики-записи об алгоритмах графов, то обнаружите, что они часто дают три или четыре разных времени выполнения в зависимости от разных реализаций (с разными структурами данных). Имейте это в виду, если вы заботитесь о скорости

Answer 2

Предполагая, что у вашего графа нет циклов, иначе самый длинный путь становится неопределенным понятием, вы действительно можете иметь топологическую сортировку. Теперь вы можете пройти эту топологическую сортировку и для каждого узла вычислить его наибольшее расстояние от исходного узла, взглянув на все его предшественники и прибавив вес ребра, соединяющего их с их расстоянием. Затем выберите предшественника, который дает вам наибольшее расстояние для этого узла. Топологическая сортировка гарантирует, что все ваши предшественники уже правильно определили расстояние.

Если в дополнение к длине самого длинного пути, вы также хотите сам путь. Затем вы начинаете с узла, который дал самую длинную длину, и просматриваете все его предшественники, чтобы найти тот, который привел к этой длине. Затем повторяйте этот процесс, пока не найдете исходный узел графа.