Среднее расстояние между двумя узлами во взвешенном неориентированном дереве

Здравствуйте, я пытаюсь понять, как рассчитать среднее расстояние между двумя узлами во взвешенном неориентированном графе. Кроме того, этот граф является деревом, поэтому у него V - 1 ребер.

Я подумал об использовании Floyd Warshall для вычисления всех кратчайших путей, а затем для вычисления среднего значения. Но это оказалось бы временной сложностью O (E ^ 3). И этого действительно недостаточно.

Я также думал об использовании динамического программирования для его решения, но я действительно не понимаю, как... Может ли кто-нибудь дать мне несколько советов, пожалуйста? Я не хочу прямого ответа, просто несколько советов, чтобы я мог продолжать думать об этом :)


graph algorithm tree undirected-graph
person Noé Weeks    schedule 01.11.2017    source источник
comment
Флойд Уоршал занимается динамическим программированием, кстати   -  person Shihab Shahriar Khan    schedule 01.11.2017
comment
Верно, но для графика с V > 1000 это недостаточно быстро.   -  person Noé Weeks    schedule 01.11.2017
comment
Я не хотел этого говорить.   -  person Shihab Shahriar Khan    schedule 02.11.2017
comment
если вы нашли его на сайте программирования, не могли бы вы дать ссылку? Мы, некоторые друзья, тоже нашли это интересным.   -  person Shihab Shahriar Khan    schedule 02.11.2017
comment
Здравствуйте, я нашел его на французском сайте, поэтому на английском языке его не будет. По-видимому, существует решение за O(V) с одной DFS.   -  person Noé Weeks    schedule 02.11.2017
comment
Я и мой друг сегодня случайно нашли решение O (V). Поэтому мы с нетерпением ждали представления этого   -  person Shihab Shahriar Khan    schedule 02.11.2017
comment
Молодец, какова твоя стратегия? Я думал о расчете для каждой вершины, в скольких путях она используется. Но у меня проблемы с реализацией   -  person Noé Weeks    schedule 02.11.2017
comment
Подумайте о каждом ребре и о том, сколько раз оно используется. Если дерево имеет размер N, а для ребра, соединяющего родительский и дочерний элементы, размер дочернего поддерева равен P, то это ребро используется P*(N-P). раз   -  person Shihab Shahriar Khan    schedule 02.11.2017
comment
Да, это звучит правильно, я попытаюсь реализовать это и скажу вам, если это сработает!   -  person Noé Weeks    schedule 02.11.2017

Ответы (1)


arrow_upward
0
arrow_downward

Создайте и поддерживайте таблицу всех кратчайших путей (неудивительно). Каждая запись включает минимальную известную стоимость и путь.

Запустите таблицу, заполнив все ребра (только пути длины 1); остальные записи inf.

Переберите таблицу, рассматривая два случая: добавьте узел слева и добавьте узел справа. На каждом конце рассмотрим только узлы, достижимые одним ребром из конечного узла. Этот путь короче, чем существующая запись?

Например, предположим, что у нас есть ребро между узлами I и J; назовите его IJ, у нас также есть край JK. Стоимость IJ + JK меньше, чем текущая запись для Edge IK? Если это так, замените его и запишите путь IJK; если нет, перейдите к следующему ребру/узлу/пути.

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

Продолжайте процесс, пока не выполните полный проход по графику без обновлений. Если вы поддерживаете этот индекс вложенного пути, я думаю, вы можете сделать это всего за один или два прохода по графу. Я считаю, что это сделало бы процесс O(E*N^2) (на ребрах и узлах).

person Prune    schedule 01.11.2017
comment
Привет, это должно работать, но недостаточно сложно:/ - person Noé Weeks; 02.11.2017