Хороший алгоритм для нахождения диаметра (разреженного) графика?

Ответ 1

Ну, я немного подумал о проблеме и немного искал в googling, и мне очень жаль, но я не могу найти алгоритм, который, кажется, не "просто найти все пары кратчайший путь".

Однако, если вы предполагаете, что Floyd-Warshall - единственный алгоритм для вычисления такой вещи (Big-Theta of | V | ^ 3), то у меня для вас есть несколько хороших новостей: алгоритм Джонсона для разреженных графиков ( спасибо, trusty CLRS!) вычисляет все пары кратчайших путей в (Big-Oh (| V | ^ 2 * lgV + VE)), что должно быть асимптотически быстрее для разреженных графиков.

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

Есть ли что-нибудь еще о графике, который может быть полезен? Если его можно легко сопоставить с 2D-плоскостью (поэтому его плоские и весовые коэффициенты подчиняются неравенству треугольника [возможно, потребуется выполнить более строгие требования, я не уверен]), вы можете вырвать некоторые геометрические алгоритмы (выпуклая оболочка может работать в nlogn, и найти самую далекую пару точек легко оттуда).

Надеюсь, это поможет! - Агор

Изменить: я надеюсь, что ссылка работает сейчас. Если нет, просто перейдите в Google.:)

Ответ 2

Я не знаю лучшего метода вычисления диаметра, отличного от всех кратчайших путей, но Mathematica использует следующее приближение для PseudoDiameter:

• Геодезическая графа - это кратчайший путь между двумя вершинами графа. Диаметр графа является самым длинным возможная длина всего графика геодезических графа. PseudoDiameter находит приблизительный диаметр графа. Он работает, начиная из вершины u и найдет вершину v который находится дальше всего от u. Эта процесс повторяется обработкой v как новая начальная вершина и заканчивается когда расстояние до графика больше не будет увеличивается. Вершина из последней уровня, который имеет наименьший степень выбрана в качестве окончательной начальная вершина u, а обход чтобы увидеть, может ли расстояние графика быть увеличенным. Это расстояние графика считается псевдо-диаметром.

http://reference.wolfram.com/mathematica/GraphUtilities/ref/PseudoDiameter.html

Ответ 3

Изменить. Я снова обнуляю, просто чтобы продолжить комментирование. У меня есть несколько комментариев по алгоритму Джонсона ниже этого ответа. - Аарон

Мой оригинальный комментарий: Мне тоже интересно об этой проблеме, но у меня нет ответа. Кажется, это связано с Minimum Spanning Tree, подграф, соединяющий все вершины, но имеющий наименьшие (или самые низкие) края, Это старая проблема с рядом алгоритмов; некоторые из которых кажутся довольно простыми в реализации.

Я изначально надеялся, что диаметр будет очевидным после обнаружения MST, но теперь я теряю надежду:-( Возможно, MST можно использовать, чтобы разместить разумную верхнюю границу диаметра, которую вы можете использовать ускорить поиск фактического диаметра?

Ответ 4

Вот некоторые мысли о том, как лучше всех пар найти кратчайшие пути на неориентированном графике, хотя я не уверен, насколько это было бы лучше.

Здесь есть подпрограмма, которая найдет два узла на расстоянии D друг от друга, если они есть. Выберите произвольный node x и вычислите M [x] = максимальное расстояние от x до любого другого node (используя любой алгоритм с самым коротким одним источником). Если M [x] >= D, то x является одним из наших узлов, а другое легко найти. Однако, если M [x] D, то ни конечная точка, которую мы ищем, может быть меньше расстояния D - M [x] от x (потому что есть пути от этого node ко всем остальным узлам через x, расстояния < D). Поэтому найдите все узлы расстояния меньше D-M [x] от x и отметьте их как плохие. Выберите новый x, на этот раз убедившись, что мы удалим все узлы, отмеченные как плохие, и повторяем. Надеемся, что мы будем отмечать множество узлов так же плохо, поэтому нам придется делать намного меньше, чем | V | кратчайшие пути.

Теперь нам просто нужно установить D = diam (G) и выполнить описанную выше процедуру. Мы не знаем, что такое diam (G), но мы можем получить для него довольно жесткий диапазон, как для любых x, M [x] <= diam (G) <= 2M [x]. Выберите несколько x для начала, вычислите M [x] для каждого и вычислите верхнюю и нижнюю границы на diam (G). Затем мы можем выполнить двоичный поиск в результирующем диапазоне, используя описанную выше процедуру, чтобы найти путь к предполагаемой длине, если таковой имеется.

Конечно, это неориентировано только. Я думаю, вы могли бы сделать аналогичную схему с ориентированными графами. Плохие узлы - это те, которые могут достигать x меньше, чем D-M [x], а верхняя граница на diam (G) не работает, поэтому вам нужен более широкий бинарный диапазон поиска.

Ответ 5

Не уверен, соответствует ли он законопроекту, но интересен:

HADI: быстрое определение диаметра и добыча в массивных графах с Hadoop

U. Кан, К. Цуракакис, А. П. Аппель, К. Фалутос, Дж. Лесковец, "HADI: оценка быстрых диаметров и добыча в массивных графах с Hadoop", CMU ML Tech Report CMU-ML-08-117, 2008.

Ответ 6

если граф является деревом (и неориентирован). вы можете просто запустить 2 dfs. Начните с произвольного node u и dfs, чтобы найти самый дальний node v. Затем начните с v и найдите самую дальнюю длину. Эта длина оптимальна

Ответ 7

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

"Диаметр" становится трудно определить с точки зрения "самого длинного пути", если граф не является деревом или DAG. "Самый длинный" путь может быть бесконечным, если на графике есть циклы. Следовательно, простой обход графа не может дать самый длинный путь по всем узлам. Поскольку вы уже заявили, что ваш график не обязательно ацикличен, и вас интересует "самый длинный самый короткий" путь, похоже, не существует какого-либо метода, который может избежать поиска кратчайшего пути для всех узлов. Использование алгоритма Джонсона, как предположил Агор, вероятно, лучше всего подходит для этого.

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

Ответ 8

Простите меня, если мой ответ неверен с точки зрения синтаксиса, но мой курс Algorithm был давно (а не на английском).

Если я правильно понимаю вашу проблему, вы хотите узнать, какое максимальное число вы можете рассчитывать, начиная с node A и доходя до node B без "повторной проверки" ваших шагов. Если это так, я бы предположил, что ваш график как ациклический (циклический вариант появится позже).

Прежде всего, верхний предел - это количество ребер. Как я вижу дело: возьмите один node, создайте дерево, где node находится в корне, и каждый последующий node, который вы можете достичь, находится на следующем уровне. Высота дерева, который вы строите, - это диаметр, а листья - это узлы, которые находятся на этом расстоянии. Если это расстояние = количество ребер, вы закончили. Если нет, выберите другой node и повторите.

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

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

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

Ответ 9

Один из способов получить оценку этого числа - начать с произвольной точки и выполнить алгоритм "травяной огонь" с шириной в ширину, обозначая кратчайшее расстояние до каждого node. Самое длинное расстояние здесь - ваша оценка.

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

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

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

Ответ 10

Выберите вершину v и сделайте BFS (v), это вычислит расстояние от v для всех вершин. Получите самое длинное расстояние. Это O (V + E)

Теперь запустите этот алгоритм для всех v вершин и выберите максимум этих самых длинных расстояний. Общая сложность: O (V * (V + E))

Ответ 11

Возможно, вам не придется вычислять ВСЕ пары, потому что в неориентированном графе есть доступная верхняя граница, и она может двигаться вниз.

Когда Breath-First-Search (BFS) выполняется из произвольного узла, он может дать список всех других узлов, отсортированных по расстоянию. Конечно, самое длинное расстояние - это нижняя граница диаметра и кандидат на него.

Два верхних расстояния, сложенные вместе - это верхняя граница диаметра, который вы ищете. Принимая эти два верхних, вы можете исключить любые узлы, для которых вы уже сделали BFS, поскольку вы уже знаете кандидатов в диаметры, которые используют эти узлы в качестве конечной точки. При назначении более длинных узлов расстояния следующим узлам, выполняющим BFS, верхняя граница в конечном итоге достигнет нижней границы. Это может произойти, прежде чем вы сделали все пары.

Ответ 12

Грязный метод:

Мы знаем, что для графа G (V, E) с | V | = n и | E | = m алгоритм Дейкстра работает в O(m+nlogn), и это для одного источника. Для вашей проблемы с парами вам нужно запустить Dijkstra для каждого node в качестве отправной точки.

Однако, если у вас много машин, вы можете легко выполнить параллельный процесс.

Этот метод проще всего реализовать, определенно не очень хорошо.

Ответ 13

Да, есть лучший способ найти Диаметр графика. Здесь я сделал простой класс, чтобы продемонстрировать это. Вершины будут точками на вашем графике.

public class MyTestClass
{
    //Simple Point struct
    struct Vertex
    {
        public float X, Y;
        public Vertex(float pX, float pY)
        {
            X = pX;
            Y = pY;
        }
    }

    //For getting the bounds of your graph
    struct BoundingBox
    {
        public float Left, Right, Bottom, Top;
        public BoundingBox(float pLeft, float pRight, float pBottom, float pTop)
        {
            Left = pLeft;
            Right = pRight;
            Bottom = pBottom;
            Top = pTop;
        }
    }

    //Properties
    Vertex[] vertices;
    BoundingBox bound;
    float diameter;

    //Constructor
    //Here is the fastest way to get the diameter >>
    public MyTestClass()
    {
        //Init objects
        vertices = new Vertex[100];
        for(int i = 0; i != vertices.Length; ++i) vertices[i] = new Vertex(i, i);
        bound = new BoundingBox(vertices[0].X, vertices[0].X, vertices[0].Y, vertices[0].Y);
        //Calculate BoundingBox
        for(int i = 0; i != vertices.Length; ++i)
        {
            bound.Left = (vertices[i].X <= bound.Left) ? vertices[i].X:bound.Left;
            bound.Right = (vertices[i].X >= bound.Right) ? vertices[i].X:bound.Right;
            bound.Bottom = (vertices[i].Y <= bound.Bottom) ? vertices[i].Y:bound.Bottom;//NOTE: If Y is faces down, then flip bottom & top comparison
            bound.Top = (vertices[i].Y >= bound.Top) ? vertices[i].Y:bound.Top;
        }
        //Messure Size of the BoundingBox
        float vecX = (bound.Right-bound.Left);
        float vecY = (bound.Top-bound.Bottom);
        diameter = (float)System.Math.Sqrt((vecX*vecX) + (vecY*vecY));
    }
}