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

Question

Я работаю в предыдущие годы Программирование ACM Проблемы с конкуренцией, пытаясь улучшить решение проблем Графа.

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

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

// 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 - Connect - Node 4. Расстояние/Вес 14

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

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

Answer 1

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

• Floyd Warshall algorithm
• Johnson's algorithm.

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

Answer 2

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

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

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

Answer 3

Итак, существует реализация Dijkstra, которая запускает O (VlogV + E), давая вашему подходу сложность примерно V^2logV + VE. См. DADS. Но, возможно, более интуитивным было бы запустить один из всех алгоритмов pairs shortest path, таких как Floyd-Warshall или Johnsons. К сожалению, все они примерно равны O (V^3) для плотных графов (близких к полному графу, где E = V^2).

Answer 4

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

Answer 5

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

вир I, J {инф I, J {п: п = длина пути между I и J} }

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

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

вир I, J {п: п = длина пути между I и J}

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

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

Answer 6

Является ли это Roads in the North проблема?