Как найти расстояние между двумя наиболее широко разнесенными узлами

Question

Я работаю над проблемами ACM Programming Competition предыдущих лет, пытаясь лучше справиться с решением задач Graph.

Сейчас я работаю над тем, чтобы мне дали произвольное количество ненаправленных узлов графа, их соседей и расстояния для ребер, соединяющих узлы. Что мне НУЖНО, так это расстояние между двумя самыми дальними узлами от друг друга (весовое расстояние, а не # узлов).

Теперь у меня есть алгоритм Дейкстры в виде:

// Dijkstra's Single-Source Algorithm
private int cheapest(double[] distances, boolean[] visited)
{
        int best = -1;
        for (int i = 0; i < size(); i++)
        {
                if (!visited[i] && ((best < 0) || (distances[i] < distances[best])))
                {
                        best = i;
                }
        }
        return best;
}

// Dijkstra's Continued
public double[] distancesFrom(int source)
{
        double[] result = new double[size()];
        java.util.Arrays.fill(result, Double.POSITIVE_INFINITY);
        result[source] = 0; // zero distance from itself
        boolean[] visited = new boolean[size()];
        for (int i = 0; i < size(); i++)
        {
                int node = cheapest(result, visited);
                visited[node] = true;
                for (int j = 0; j < size(); j++)
                {
                        result[j] = Math.min(result[j], result[node] + getCost(node, j));
                }

        }
        return result;
}

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

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

Вот пример ввода для задачи:

Всего узлов: 5

Ребра:
Узлы 2 - Соединение - Узел 4. Расстояние / Вес 25
Узлы 2 - Соединение - Узел 5. Расстояние / Вес 26
Узлы 3 - Соединение - Узел 4. Расстояние / Вес 16
Узлы 1 - Соединение - Узел 4. Расстояние / Вес 14

Ответ на этот пример ввода «67 миль». Какова длина дороги между двумя наиболее широко разделенными деревнями.

Так я должен сделать это так, как я описал, или есть намного более простой и гораздо менее дорогостоящий способ?

Answer 1

Похоже, вы можете использовать любой из:

• Алгоритм Флойда Варшалла
• Алгоритм Джонсона .

Я не могу дать вам много советов о них - я не эксперт.

Answer 2

Итак, есть реализация Dijkstra, которая запускает O (VlogV + E), давая вашему подходу сложность примерно V ^ 2logV + VE. См. Папа . Но, возможно, более интуитивно понятным было бы запустить один из всех алгоритмов кратчайшего пути , таких как Флойд-Варшалл или Джонсонс. К сожалению, они все примерно O (V ^ 3) для плотных графов (близко к полному графу, где E = V ^ 2).

Answer 3

Это проблема Дороги на севере ?

Answer 4

Если вы хотите самый длинный кратчайший путь, который

sup i, j {inf i, j {n: n = длина пути между i и j}}

вы, безусловно, должны рассмотреть алгоритм кратчайшего пути для всех узлов, такой как Flyod-Warshall, как упоминалось другими. Это будет в порядке O (V ^ 3).

Если вы хотите самый длинный путь, который

sup i, j {n: n = длина пути между i и j}

Вы можете попытаться использовать идею Мидхата. (которая на самом деле так же сложна, как и первоначальная проблема, как указано в комментариях). Я бы рекомендовал инвертировать веса с 1 / w, чтобы сохранить положительные веса, учитывая, что исходные веса были строго положительными.

Другим алгоритмом, который вы можете использовать при работе с отрицательными весами, является алгоритм Беллмана и Форда

Answer 5

Умножьте веса ребер на -1 и найдите кратчайший путь на новом графике. Это будет самый длинный путь на исходном графике

Answer 6

Вы можете использовать реализацию Дейкстры следующим образом:

1. Выберите случайный узел, (a), запустите Dijkstra из узла a и найдите самый дальний узел из него. Отметить этот узел как узел b.
2. Запустите Dijkstra снова, начиная с узла b, и найдите самый дальний узел от него. Отметить этот узел как узел c.

У меня нет доказательств этого, но я думаю, что b и c будут самыми дальними узлами. Возможно, вам придется выполнить еще одну итерацию (я все еще думаю об этом).