окт.2017. кратчайший путь от каждого к каждому узлу….
Алгоритм Дейкстры 1959 года — самый известный, а может быть, и самый быстрый; позвольте мне представить еще один алгоритм.
2 вида проблем.
пусть это будет ориентированный граф, ребра которого оценены.
первая задача: найдите кратчайшее расстояние от узла A до узла B. Answer=9
Алгоритм Роя относится к этому типу.
еще одна проблема: дайте мне кратчайший путь от узла А к узлу Б.
Ответ=А-У-В-В-Б. Алгоритм Дейкстры относится к этому типу.
Конечно, знание A-U-V-W-B позволяет рассчитать точное значение расстояния путем сложения значений ребер AU, UV, VW и WB.
Алгоритм Роя, 1959 г., для каждого кратчайшего расстояния (задача первого рода).
Впервые я прочитал объяснение Роя — Рой, Бернар (1959). Transitivité et connexité. К. Р. акад. науч. Париж. 249: 216–218, всего 3 страницы — я был полностью сбит с толку. Так что не бойтесь, время на вашей стороне. Я даю вам расшифровку этого алгоритма в псевдо-Python-коде.
Довольно просто, не так ли?
Строки 0–20 являются инициализациями.
* несуществующие изгороди обнуляются до «бесконечности»
* главная диагональ обнуляется, потому что расстояние между i и i равно нулю.
строка 21 — это начало алгоритма Роя. Этот алгоритм представляет собой простой цикл с индексом «i».
Строки 24–37 являются «i-преобразованием» матрицы dist. Объяснение «i-преобразования» дано ниже.
Математика расстояний.
Этот алгоритм работает по 8 правилам:
мы манипулируем набором чисел с характеристиками:
*законом сложения
**с нейтральным элементом (нулем),
**ассоциативно слева и справа,
*отношение порядка
** ноль меньше любого числа
** бесконечность является поглощающим элементом, больше любого другого числа
** бесконечность+бесконечность=бесконечность
** бесконечность+ноль=бесконечность
** бесконечность+x=бесконечность
* треугольное неравенство dist(hi)+dist(ik)≥dist(hk)
«Я-трансформация» Роя, определение.
Пусть A — матрица расстояний ориентированного графа.
Пусть я вершина.
«I-преобразование» Роя, называемое TI, представляет собой преобразование матрицы A, например:
B — матрица той же размерности, что и A.
TI( A )=B
Bhk = Ahk, если Ahi+Aik≤Ahk
иначе: Bhk = Ahi+Aik
A small визуализация:
Если набор вершин равен {h, i, j, k, l,…. w,x,y,z}
набор преобразований {TH,TI,…..TW,TX,TY,TZ}, конечно.
Вы можете комбинировать преобразования, например
TZ( TW ( A )) = новая матрица.
«Я-преобразования» Роя, всего 2 свойства.
- I-преобразование является идемпотентным,то есть
( TI )² = (TI)
посмотрите на алгоритм:
«# начало алгоритма
для i в вершинах:
….# начало I-преобразования *******
…. etc….»
Вы видите только один цикл «для i в вершинах:», потому что нет необходимости делать еще раз то же самое преобразование с тем же «i» - комбинация двух преобразований является коммутативной,
TZ( TW ( A )) = TW( TZ ( A )), - поэтому в псевдокоде меня не волнует порядок «i s» в списке «вершин». Следовательно, строка 3 «vertices = (из input_matrix, извлечь список вершин)» достаточно неточна, чтобы можно было построить неупорядоченный список вершин.
примечание: демонстрация Роя этой коммутативности коротка, но очень сложна, я не буду ее объяснять. в этом посте. - * бонус. Хитроумный трюк: я всегда работаю с одной и той же матрицей dist, меняя только одну ячейку внутри тройного цикла i h k, потому что промежуточные состояния dist не сохраняются. Это не уловка Роя!
- * бонус. И последний фокус: обратите внимание на 3 цикла с упорядоченными индексами i,h,k.
это не h,i,k! «i» — это индекс I-преобразования, .
«h» и «k» — просто исчерпывающий перечень пар узлов внутри области действия одного I-преобразования.
Связность графа, кратчайшее расстояние, кратчайший путь.
Простое соединение.
Чтобы быть правдой, позвольте мне сказать, что статья Роя 1959 года
Рой, Бернар (1959). Transitivité et connexité. К. Р. акад. науч. Paris — речь шла только о связности в графе, матрица A состоит только из 0/1,
Aij = 0 означает, что i и j не связаны
Aij = 1 означает, что между i и j существует хотя бы один путь,
1 — нейтральный элемент, 0 — поглощающий элемент,
и 0+1=0; 1+1=1; 1+0=0; 0+0=0, конечно.
Бернар Рой — французский математик, см. https://fr.wikipedia.org/wiki/Bernard_Roy
Кратчайшие расстояния.
Приведенная выше псевдопрограмма вычисляет только матрицу расстояний, а не описание путей. Она относится к первому типу проблем. Некоторые называют его алгоритмом Флойда-Уоршалла, 1962 г., см. https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm.
Мне больше нравится «алгоритм Роя-Флойда-Уоршалла».
Сложность этого алгоритма равна n**3 из-за тройного цикла i,h,k; n — количество вершин.
Кратчайшие пути.
Это второй тип проблем. Если вам нужен не только массив кратчайших расстояний, но и описание путей, вы можете воспользоваться техникой реконструкции пути, описанной в
https://en.wikipedia.org/ wiki/Floyd%E2%80%93Warshall_algorithm
Отличие от алгоритма Джикстры только в точке «h» отправления. Раньше Джикстра работал с одним узлом отправления.
Таким образом, алгоритм Роя-Флойда-Уоршалла равен n алгоритмам Джикстры.
Дальнейшие алгоритмы.
Понятия
- И-Трансформации
- и тройной петли Роя
- может использоваться для вычисления многих других вещей в графе, например, компонентов соединения, даже самых длинных путей! С множеством адаптаций, но это уже другая история.
