Самый длинный путь в графе

Question

Начиная с последних 2 дней, я пытаюсь найти некоторую логику для вычисления самого длинного пути в графе. Я знаю, что могу легко найти его для DAG, и в целом это алгоритм за полиномиальное время. Формально я хочу реализовать эвристику для вычисленийсамый длинный путь, более того, если задана вероятность p, с которой в графе присутствует ребро, как мы можем решить эту проблему ... help ...

Answer 1

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

public class LongestPath {
static int times;
public double initLongestPath(ArrayList<Vertex> V,Vertex source){
    for(Vertex u:V){
        u.setVisited(false);
    }
    return getLongestPath(source);
}
public double getLongestPath(Vertex v){
    ++times;
    System.out.println(times);
    double w,dist,max=0;
    v.setVisited(true);
    for(Edge e:v.getOutGoingEdges()){
        if(!e.getToNode().isVisited()){
            dist=e.getWeight()+getLongestPath(e.getToNode());
            if(dist>max)
                max=dist;
        }
    }

    v.setVisited(false);    
    return max;
}

}

Answer 2

Дейкстры нельзя использовать на графах с отрицательными весами - Вики-статья о Дейкстре

Алгоритм Дейкстры, разработанный голландским ученым-компьютерщиком Эдсгером Дейкстрой в 1956 году и опубликованный в 1959 году, 1 - это алгоритм поиска графа, который решает проблему кратчайшего пути из одного источника для графа с неотрицательными затратами на ребро пути ...

Таким образом, вы не можете свести на нет все веса ребер и использовать Dijkstra, что вы можете сделать, это свести на нет все веса ребер и использовать алгоритм Беллмана-Форда - Wiki статья о Беллман-Форде

Алгоритм Беллмана – Форда - это алгоритм, который вычисляет кратчайшие пути от одной исходной вершины ко всем остальным вершинам взвешенного орграфа. 1 Он медленнее, чем алгоритм Дейкстры для той же задачи, но более универсален,поскольку он способен обрабатывать графики, в которых некоторые веса ребер равны отрицательным числам

РЕДАКТИРОВАТЬ: кратчайший путь (снаиболее отрицательное значение) - это самый длинный путь в исходном графе.

ПРИМЕЧАНИЕ: если у вас есть положительные циклы на вашем графике, вы не найдете решения, так как самый длинный путь не существует в таком графике.

Answer 3

Вы всегда можете просто использовать поиск в ширину (BFS), и всякий раз, когда вы добавляете ребро в график, вы получаете его стоимость в качестве аддитивного обратного (умножьте его на -1). Таким образом, вы найдете «кратчайший путь», используя самые длинные ребра. Поскольку вы выполняете скалярное преобразование, вы не теряете возможность добавлять в группу (которую вы теряете, если используете обратное мультипликативное выражение).

Answer 4

Инвертирование весов путей и запуск алгоритма кратчайшего пути.Наименьшее полученное вами число (самое отрицательное) - это самый длинный путь.