Теория графов Алгоритм динамического программирования - Кратчайший путь Флойда

предисловие

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

Алгоритм Флойда

Floyd — это классический алгоритм кратчайшего пути с несколькими источниками, который использует идею динамического программирования для поиска кратчайшего пути между точками с несколькими источниками в заданном взвешенном графе, а временная сложность алгоритма составляет O(n3). Он называется Флойд, потому что одним из изобретателей алгоритма был Роберт Флойд, лауреат премии Тьюринга 1978 года и профессор компьютерных наук в Стэнфордском университете.

смысл

Для взвешенного графа с n точками, начиная с матрицы весов взвешенного графа, рекурсивно обновить n раз и, наконец, получить матрицу кратчайшего пути между каждыми двумя точками. То есть матрица смежности взвешенного графа равна $D=(d_{ij})_{n \times n}$ , рекурсивно обновить матрицу по определенной формуле, исходная матрица D(0), первый раз D(0) используется для построения матрицы D(1) по формуле, второй раз D (1) используется по формуле Построить матрицу D(2) и так далее, построить матрицу D(n) с D(n-1) по формуле, D(n) — матрица расстояний граф, i строка j столбец представляет вершину i до вершины j кратчайшее расстояние.

динамическое программирование

Как понять этот алгоритм динамического программирования? Это можно понимать как выбор точки передачи по одной, а затем для точки передачи все остальные точки, использующие ее в качестве точки передачи, должны быть обновлены в соответствии с регламентом матрицы расстояний. Например, если в качестве точки перехода выбрано «1», исходное расстояние между «02» равно 5. После прохождения через точку перехода 1 (т. е. путь становится «012») расстояние равно 4, что становится меньше, затем обновите соответствующий элемент матрицы расстояний с 5 до 4. Когда все вершины в графе обрабатываются как транзитные точки, итоговая полученная матрица расстояний является матрицей кратчайших расстояний с несколькими источниками.

Предполагать c(i,j,k) Кратчайшее расстояние, на котором номер промежуточного узла от i до j не превышает k, когда k=0, $c(i,j,0)=d_{ij}$ , для графа с n вершинами кратчайшее расстояние от i до j, которое нам требуется, равно c(i,j,n-1) .

Теперь мы строим c(i,j,k) и c(i,j,k-1) Рекурсивная связь между , для любого k, c(i,j,k)=min(c(i,j,k-1),c(i,k,k-1)+c(k,j,k-1)) , то по рекурсивной зависимости можно получить конечный кратчайший путь, то есть кратчайшее расстояние, где число промежуточных узлов не превышает n-1.

Алгоритмический процесс

Начиная с любого одностороннего пути, расстояние между всеми двумя точками является весом ребра, и если между двумя точками нет ребра, вес бесконечен. готовый массив $D=(d_{ij})_{n \times n}$ Чтобы записать кратчайшее расстояние между i и j, сначала, если i=j, то dis[i][j]=0. Если две точки i и j соединены, значением dis[i][j] является вес ребра. Если две точки i и j не соединены, значение dis[i][j] бесконечно.
Для каждой пары вершин u и v посмотрите, есть ли вершина w, которая делает путь от u до w до v короче, чем известный путь, и обновите, если это так. То есть для всех k значений (1

Волшебные пять строк кода

Ядром алгоритма Флойда являются следующие пять строк кода. Вы можете убедиться, что три цикла for вложены друг в друга. Крайний k - это ситуация, когда цикл принимает разные точки перехода. Пусть каждая вершина в графе используется в качестве точки перехода к обновить расстояние.После всех циклов это окончательная кратчайшая матрица расстояний.

for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++) 
            if(d[i][k]+d[k][j]<d[i][j]) 
                    d[i][j]=d[i][k]+d[k][j];

Преимущества и недостатки

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

Недостатки: относительно высокая временная сложность, и он не подходит для расчета большого объема данных.

Процесс реализации

Для неориентированного взвешенного графа с 7 вершинами 0-6 используются для представления каждой вершины графа, а число на каждом ребре является соответствующим весом.

Сначала матрица расстояний инициализируется в соответствии с весом каждого ребра. Это матрица [7x7]. Строки и столбцы соответствуют двум вершинам. Например, 0-я строка и 1-й столбец представляют вершину от 0 до вершины 1. , и соответствующее значение равно 3, то есть вес Значение равно 3. По аналогии другие элементы представляют веса соответствующих ребер соответственно.

При выборе вершины 0 в качестве транзитной точки

Посмотрите один за другим, чтобы увидеть, есть ли 0 в качестве точки перехода, чтобы сократить расстояние На самом деле нет необходимости сравнивать элементы всех матриц, просто сравните удовлетворенностьif (i != j && j != k && i != k)Элементы условия, то есть диагональную линию с 0 и строку и столбец, соответствующие точке перехода, сравнивать не нужно, поскольку элементы на диагонали представляют собой расстояние от вершины до самой себя, поэтому нет необходимо сравнить, а строка и столбец, соответствующие точке передачи, представляют собой вершину для передачи.Расстояние точек не нужно сравнивать.

сравниватьd[1][2]иd[1][0]+d[0][2], т.к. 1d[1][2].

вниз, сравнитеd[1][3]иd[1][0]+d[0][3], т.к. 4d[1][3].

вниз, сравнитеd[1][4]иd[1][0]+d[0][4], не обновлено, так как INFd[1][4]. затем внизd[1][5],d[1][6]Ситуация аналогична для обоих элементов.

сравниватьd[2][1]иd[2][0]+d[0][1], т.к. 1d[2][1].

вниз, сравнитеd[2][3]иd[2][0]+d[0][3], т.к. 4d[2][3].

вниз, сравнитеd[2][4]иd[2][0]+d[0][4], т.к. 8d[2][4].

вниз, сравнитеd[2][5]иd[2][0]+d[0][5], т.к. 2d[2][5].

вниз, сравнитеd[2][6]иd[2][0]+d[0][6], т.к. INFd[2][6].

сравниватьd[3][1]иd[3][0]+d[0][1], так как 4d[3][1].

Аналогично все остальные элементы не обновляются, и сравнение завершается в концеd[6][5]иd[6][0]+d[0][5]После этого все операции сравнения с 0 в качестве точки переноса завершаются.

При выборе вершины 1 в качестве транзитной точки

Найдите их один за другим, чтобы увидеть, есть ли транзитная точка с 1, чтобы сократить расстояние, сравнитеd[0][2]иd[0][1]+d[1][2],

Поскольку 5>3+1, мы будемd[0][2]Значение обновлено до 4.

сравниватьd[0][3]иd[0][1]+d[1][3],

Поскольку INF>3+4, будетd[0][3]Значение обновлено до 7.

Следующие три элемента в строке 0 не обновляются, а после строки 2 сравнитеd[2][0]иd[2][1]+d[1][0],

Так как 5>1+3, мы будемd[2][0]Значение обновлено до 4. Ни один из оставшихся элементов во второй строке не нуждается в обновлении.

Стартовая строка 3, сравнитеd[3][0]иd[3][1]+d[1][0],

Поскольку INF>4+3, будетd[3][0]Значение обновлено до 7.

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

При выборе вершины 2 в качестве транзитной точки

Узнайте один за другим, чтобы увидеть, есть ли транзитная точка с 2, чтобы сократить расстояние, сравнитеd[0][1]иd[0][2]+d[2][1], так как 3d[0][1]Не обновлять.

сравниватьd[0][3]иd[0][2]+d[2][3], поскольку 7d[0][3]Не обновлять.

сравниватьd[0][4]иd[0][2]+d[2][4],

Поскольку INF>4+8, будетd[0][4]Значение обновлено до 12.

Аналогичным образом сравните и обновите все оставшиеся элементы с вершиной 2 в качестве точки перехода.

При выборе вершины 3 в качестве транзитной точки

Узнайте один за другим, чтобы увидеть, есть ли 3 в качестве точки передачи, чтобы сократить расстояние, сравнитеd[0][1]иd[0][3]+d[3][1], поскольку 3d[0][1]Не обновлять.

сравниватьd[0][2]иd[0][3]+d[3][2], поскольку 4d[0][2]Не обновлять.

Аналогичным образом сравните и обновите все оставшиеся элементы с вершиной 3 в качестве точки перехода.

При выборе вершины 4 в качестве транзитной точки

Проверьте один за другим, чтобы увидеть, есть ли 4 в качестве точки передачи, чтобы сократить расстояние, сравнитеd[0][1]иd[0][4]+d[4][1], поскольку 3d[0][1]Не обновлять.

сравниватьd[0][2]иd[0][4]+d[4][2], поскольку 4d[0][2]Не обновлять.

Аналогичным образом сравните и обновите все оставшиеся элементы с вершиной 4 в качестве точки перехода.

При выборе вершины 5 в качестве транзитной точки

Проверьте один за другим, чтобы увидеть, есть ли 5 в качестве точки передачи, чтобы сократить расстояние, сравнитеd[0][1]иd[0][5]+d[5][1], поскольку 3d[0][1]Не обновлять.

сравниватьd[0][2]иd[0][5]+d[5][2], так как 4d[0][2]Не обновлять.

Аналогичным образом сравните и обновите все оставшиеся элементы с вершиной 5 в качестве точки перехода.

При выборе вершины 6 в качестве транзитной точки

Проверьте один за другим, чтобы увидеть, есть ли 6 в качестве точки передачи, чтобы сократить расстояние, сравнитеd[0][1]иd[0][6]+d[6][1], поскольку 3d[0][1]Не обновлять.

сравниватьd[0][2]иd[0][6]+d[56][2], поскольку 4d[0][2]Не обновлять.

Аналогичным образом сравните и обновите все оставшиеся элементы с вершиной 6 в качестве точки перехода.

окончательная матрица

После того, как все вершины обработаны как транзитные, окончательно получается матрица, которая является матрицей кратчайших расстояний каждой вершины графа. Напримерa[0][4]=12То есть кратчайшее расстояние от вершины 0 до вершины 4 равно 12. При этом видно, что матрица расстояний симметрична относительно диагональной линии.

------------- Рекомендуем прочитать ------------

Краткое изложение моих проектов с открытым исходным кодом (машинное и глубокое обучение, НЛП, сетевой ввод-вывод, AIML, протокол mysql, чат-бот)

Зачем писать «Анализ проектирования ядра Tomcat»

Резюме моей статьи за 2017 год — машинное обучение

Краткое изложение моих статей за 2017 год — Java и промежуточное ПО

Резюме моих статей 2017 года — глубокое обучение

Краткое изложение моих статей за 2017 год — исходный код JDK

Резюме моей статьи за 2017 год — обработка естественного языка

Резюме моих статей 2017 года — Java Concurrency

Поговори со мной, задай мне вопросы:

Добро пожаловать, чтобы следовать: