Найти кратчайший цикл в ориентированном взвешенном графе

Question

Где длина ребер положительна, и она должна выполняться за O (V ^ 3) времени. У меня возникли некоторые проблемы, когда я пытаюсь обдумать эту проблему, но сейчас у меня есть следующее:

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

С этой реализацией тогда, так как я go через каждую вершину для каждой вершины в двойном для l oop это O (V ^ 3), но я использую алгоритм Джисктра дважды в каждой итерации двойного для l oop, так что это O (ElogV). Я не совсем уверен, как это будет O (V ^ 3), поэтому я думаю, что моей реализации может потребоваться больше работы.

Answer 1

Для реализации O (V³) вы можете проверить, составляют ли каждые 3 вершины цикл и вернуть те с минимальным общим весом:

int minimalCycleWeight = POSITIVE_INFINITY;
// declare nodes to be returned if needed

for (int i = 0; i < verticesCount; i++) {
    for (int j = 0; j < verticesCount; j++) {
        for (int k = 0; k < verticesCount; k++) {
            if (graph[i].hasEdgeTo(graph[j]) 
                && graph[j].hasEdgeTo(graph[k])
                && graph[k].hasEdgeTo(graph[i])) {

                int totalCycleWeight = graph[i].weightTo(graph[j])
                                        + graph[j].weightTo(graph[k])
                                        + graph[k].weightTo(graph[i]);

                if (totalCycleWeight < minimalCycleWeight) { 
                    minimalCycleWeight = totalCycleWeight;
                    // save nodes to return later if needed
                }
            }
        }
    }
}

---

С помощью Дейкстры Алгоритм вы могли бы только сделать лучше , чем O (V³) .