4430
правок
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Материал из WEGA
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 18:35, 23 января 2012
, 23 января 2012→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 65: | Строка 65: | ||
(2) Рассмотрим случай с единичными стоимостями дуг. В варианте (1) вычисление свидетелей производится дополнительно, то есть не является необходимым, если нужны только кратчайшие расстояния. Чтобы получить такую же сложность для точного, а не рандомизированного алгоритма, вычисление свидетелей становится обязательным. Как было отмечено ранее, поддержка свидетелей (то есть матрицы W) вносит дополнительный полилогарифмический коэффициент, что означает, что анализ может быть сосредоточен на произведении Романи в <math>\tilde{O} </math>-нотации. Более конкретно, I выбирается в качестве <math>\ell / 3</math>-мостового множества, являющегося сильным при единичной стоимости дуг. Чтобы вычислить I как <math>O(\ell)</math>-мостовое множество, необходимо получить вершины кратчайшего пути из i в j для каждого i и j, используя матрицу свидетелей W, за время <math>O(\ell)</math>. После получения этих <math>n^2 \,</math> множеств за время <math>O(\ell n^2)</math> можно вычислить <math>O(\ell)</math>-мостовое множество размера O(n ln n/ℓ) с той же временной сложностью, как показано в [10]. Процесс вычисления мостового множества должен остановиться в <math>\ell = n^{1/2} \, </math>, поскольку после этой границы процесс становится чрезмерно дорогим; в силу этого после данной границы используется одно и то же мостовое множество. Время вычисления до этой границы остается тем же, что и в варианте (1), а после границы составляет <math>\tilde{O}(n^{2.5}) \, </math>. Таким образом, мы получаем алгоритм из двух этапов. | (2) Рассмотрим случай с единичными стоимостями дуг. В варианте (1) вычисление свидетелей производится дополнительно, то есть не является необходимым, если нужны только кратчайшие расстояния. Чтобы получить такую же сложность для точного, а не рандомизированного алгоритма, вычисление свидетелей становится обязательным. Как было отмечено ранее, поддержка свидетелей (то есть матрицы W) вносит дополнительный полилогарифмический коэффициент, что означает, что анализ может быть сосредоточен на произведении Романи в <math>\tilde{O} </math>-нотации. Более конкретно, I выбирается в качестве <math>\ell / 3</math>-мостового множества, являющегося сильным при единичной стоимости дуг. Чтобы вычислить I как <math>O(\ell)</math>-мостовое множество, необходимо получить вершины кратчайшего пути из i в j для каждого i и j, используя матрицу свидетелей W, за время <math>O(\ell)</math>. После получения этих <math>n^2 \,</math> множеств за время <math>O(\ell n^2)</math> можно вычислить <math>O(\ell)</math>-мостовое множество размера O(n ln n/ℓ) с той же временной сложностью, как показано в [10]. Процесс вычисления мостового множества должен остановиться в <math>\ell = n^{1/2} \, </math>, поскольку после этой границы процесс становится чрезмерно дорогим; в силу этого после данной границы используется одно и то же мостовое множество. Время вычисления до этой границы остается тем же, что и в варианте (1), а после границы составляет <math>\tilde{O}(n^{2.5}) \, </math>. Таким образом, мы получаем алгоритм из двух этапов. | ||
(3) Если стоимости дуг положительны и ограничены M = | (3) Если стоимости дуг положительны и ограничены <math>M = n^t > 0 \, </math>, сходная процедура может быть использована для вычисления <math>O(\ell)</math>-мостового множества размера O(n ln n/ℓ) за время <math>\tilde{O}(\ell n^2)</math>. Используя мостовое множество, задачу нахождения кратчайших путей между всеми парами вершин можно решить за время <math>\tilde{O}(n^{2 + \mu (t)}) \, </math> способом, сходным с вариантом (1). Этот результат можно обобщить на случай, когда стоимости дуг находятся в диапазоне от -M до M, сохранив ту же временную сложность, если модифицировать процедуру для вычисления <math>\ell</math>-мостового множества в случае, если не имеется отрицательных контуров. Подробности изложены в [10]. | ||
Применение | == Применение == | ||
Эксцентриситетом вершины v называется наибольшее расстояние от v до любой другой вершины графа. Диаметр графа равен наибольшему эксцентриситету для любой вершины. Иными словами, диаметр представляет собой наибольшее расстояние между любой парой вершин. Если задача нахождения кратчайших путей между всеми парами вершин решена, максимальный элемент матрицы будет равен ее диаметру. | Эксцентриситетом вершины v называется наибольшее расстояние от v до любой другой вершины графа. Диаметр графа равен наибольшему эксцентриситету для любой вершины. Иными словами, диаметр представляет собой наибольшее расстояние между любой парой вершин. Если задача нахождения кратчайших путей между всеми парами вершин решена, максимальный элемент матрицы будет равен ее диаметру. | ||
Открытые вопросы | == Открытые вопросы == | ||
Среди оставшихся нерешенными задач особенно выделяются две. Первая заключается в уменьшении сложности | Среди оставшихся нерешенными задач особенно выделяются две. Первая заключается в уменьшении сложности <math>\tilde{O}(n^{2.575}) \, </math> при нахождении кратчайших путей между всеми парами вершин графа с дугами единичной стоимости. Вторая состоит в улучшении границы <math>M < O(n^{0.624}) \, </math> сложности алгоритма нахождения кратчайших путей между всеми парами вершин графа, стоимости дуг которого являются целыми числами не более M, и достижении значений ниже кубических. | ||
Перекрестные ссылки | == Перекрестные ссылки == | ||
► Алгоритм поиска кратчайших путей в разреженных графах | ► Алгоритм поиска кратчайших путей в разреженных графах | ||
► Полностью динамический алгоритм нахождения кратчайших путей между всеми парами | ► Полностью динамический алгоритм нахождения кратчайших путей между всеми парами | ||
