Брайан уже ответил на ваш вопрос выше, но я подумал, что могу углубиться.
Во-первых, как он указал, эта проблема легко разрешима только при отсутствии циклов. Если есть циклы, вы сталкиваетесь с ситуацией, когда у вас есть бесконечно длинные пути. В этом случае вы можете определить самый длинный путь как любой путь без повторяющихся узлов. К сожалению, можно показать, что эта задача является NP-трудной. Поэтому вместо этого мы сосредоточимся на проблеме, которую вам действительно нужно решить (поскольку вы упомянули топологическую сортировку) — самом длинном пути в направленном ациклическом графе (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 для ваших узлов. Но и без этого поиск входящих ребер для каждого узла — это боль (и не производительность!). На мой взгляд, графовые алгоритмы концептуально отличаются от, скажем, алгоритмов для строк и массивов, потому что очень важна реализация! Если вы почитаете вики-статьи об алгоритмах графов, вы обнаружите, что они часто дают три или четыре разных времени выполнения, основанных на разных реализациях (с разными структурами данных). Имейте это в виду, если вам важна скорость
person
rliu
schedule
30.04.2013
