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

Question

У меня возникла проблема, мы хотим разработать эффективный алгоритм поиска простого пути с самым легким весом. (простой путь с минимальным весом).

Я думаю, что это не полиномиальное решение, но некоторые друзья говорят, что это O (n) или O (n^2) или O (n lg n) было бы ...!

программисты или эксперт, помогли бы мне? любой песокод?

РЕДАКТИРОВАТЬ:

ввода этой проблемы является деревом Т с целыми весами по краям. Веса могут быть отрицательными, нулевыми или положительными. Длина пути - это сумма весов ребер в пути. Путь прост, если никакая вершина не повторяется.

Выход: поиск наименьшего веса простой путь в данном дереве.

Answer 1

Вот псевдокод линейного решения:

res = 0 // A path from a node to itself has a weight 0 

// Runs depth first search from the v vertex and returns the weight of 
// the shortest path that starts in a descendant of v and ends in v 
def dfs(v): 
    // The shortest path from a descendant of v to v 
    minLength = 0 
    // The list of all lengths of paths coming from children 
    childLengths = [] 
    for edge in edges(v): 
     childLength = dfs(edge.to) 
     // Update the result with a vertical path from the child 
     res = min(res, childLength + edge.weight) 
     // Update the minLength based on the child's value 
     minLength = min(minLength, childLength + edge.weight) 
     childLengths.add(childLength + edge.weight) 
    if childLengths.size() >= 2: 
     // Update the result based on two smallest children values. 
     // Finds the the first and the second minimum in a list in a linear time. 
     min1 = firstMin(childLengths) 
     min2 = secondMin(childLengths) 
     res = min(res, min1 + min2) 
    return minLength  

dfs(root) 
return res 

Если дерево не укоренились, мы можем выбрать любую вершину в качестве корня.

Answer 2

В дереве существует только один простой путь между каждой парой узлов (there's a proof here).

Так что, даже если вы попробуете каждую пару узлов, которые находят путь между ними, у вас будет алгоритм O (n^3).

Один лучший способ - найти для каждого узла стоимость для каждого другого узла за один раз. Это снижает алгоритм до O (n^2).

Answer 3

Существует простой алгоритм O (n), основанный на том факте, что в дереве всегда есть несколько листьев, и если мы удалим лист, оставшийся граф все еще является деревом. Таким образом, мы можем удалить листья один за другим и обработать все дерево (все ребра) таким образом.

Вам нужно будет найти самый легкий путь для каждого узла.

Итак, давайте предположим, что вы обрабатываете некоторый лист, а узел n связан с узловым листом, и мы хотим быть уверены, что вы следите за любым путем, проходящим через край, который соединяет это n и лист. Давайте посмотрим на картину

направление здесь означает только направление от узлов, удалений раньше своих «родителей», узла, которые будут удалены позже, это может зависеть от порядка п, которые вы обрабатываете листья.

Если у нас есть кратчайший путь, проходящий через лист, и n, он может подключить любой «ребенок» к листу с каким-либо другим ребенком n или он может подключить любой «ребенок» листа к остальной части дерева.

В обоих случаях достаточно сохранить кратчайший путь от любого из уже обработанных узлов до текущего узла. Когда мы обрабатываем лист, мы берем легкий путь, основанный на листе, и добавляем вес соединения с ним и сравниваем его с самым коротким путем, уже сохраненным для n. Таким образом, мы неизбежно придем к сопоставлению двух кратчайших путей для n и сможете объединить их и иметь самый короткий путь для n, сохраненный при обработке всех «детей» из n.

Итак, вот псевдокод.

for each (node in graph) 
{ 
    node.shortest_path = 0; //zero length path from this node to this node 
} 
leaves = new list(all leaves in graph); //O(n) to find 
int minWeight = 0; //any zero length path is minimum weight path currently found 

//note that we a going to add new elements in list during the iteration 
//and we will need to iterate through all of them including new added 
//so in usual programming languages you will need to use for cycle 
for each (leaf in leaves) 
{ 
     //we will have last node in tree with no connection 
     //because we will delete it on previous iteration 
     //and we don't need to process this node 
     //for this problem it is last node, 
     //but it may be not last if we have several trees instead of one 
     if (no point connected to leaf) continue; 

    n = only one node still connected to leaf  
    connection = connection between n and leaf 

    //check if we can make a short path which goes through n 
    //from one already processed "child" node to another 
    if (leaf.shortest_path + 
     connection.weight 
     + n.shortest_path < minWeight ) 
    { 
     minWeight = leaf.shortest_path+connection.weight+n.shortest_path; 
    } 
    //and we need to keep lightest path from any processed "child" to n 
    if (leaf.shortest_path + connection.weight < n.shortest_path) 
    { 
      n.shortest_path = leaf.shortest_path + connection.weight; 
      if(n.shortest_path < minWeight) 
      { 
       minWeight = n.shortest_path; 
      } 
    } 

    //delete connection and 
    connection.delete(); 
    //if n is now leaf add it to leaf list 
    if (n is leaf) 
    { 
     leaves.Add(n); 
    } 
} 

Таким образом, в основном цикле мы обрабатывали каждый узел ровно один раз, чтобы у нас была сложность O (n). Если вам нужен ненулевой путь длины, но этот алгоритм не нашел его, это означает, что все ребра имеют положительный вес, а самый легкий путь без нулевой длины - самый легкий край.