Понимание алгоритма Флойда-Уоршалла

Первоначально опубликовано на Seedbx.com 2 декабря 2020 г.

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

В этом посте мы обсудим алгоритм Флойда-Уоршалла, который идеально подходит для этой работы.

Примечание. Во всех псевдокодах используется индексация на основе 0, а отступы используются для различения блоков кодов.

Постановка задачи

Пусть G — взвешенный ориентированный граф с положительным и отрицательным весом (но без отрицательных циклов), а V — множество всех вершин. Найдите длину кратчайшего взвешенного пути в G между каждой парой вершин в V.

Наивный подход

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

Псевдокод:

minDistance[|V|][|V|]={inf}
findShortestPath(curr, dest)
  if curr==dest
    return minDistance[curr][curr]=0
  if visited[curr]==true
    return minDistance[curr][dest]
 
  visited[curr]=true 
  sumOfWeights=minDistance[curr][dest] 
  for vertex in graph[curr] 
    ctr=graph[curr][vertex]+findShortestPath(vertex, dest) 
    if ctr<sumOfWeights 
      sumOfWeights=ctr 
  return minDistance[curr][dest]=sumOfWeights 

naive_approach() 
  for start=0 upto |V| 
    for dest=0 upto |V| 
      visited[|V|]={false} 
      foo=findShortestPath(start, dest)

Временная сложность: O(|V|2*( |V|+|E| ))

Пространственная сложность: O(|V|2)

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

Алгоритм Флойда-Уоршалла — это пример динамического программирования, опубликованный независимо друг от друга в 1962 году.

Подобно алгоритму Беллмана-Форда и алгоритму Дейкстры, он вычисляет кратчайший взвешенный путь в графе. Однако в отличие от алгоритма Беллмана-Форда и алгоритма Дейкстры, которые находят кратчайший путь из одного источника, алгоритм Флойда-Уоршалла находит кратчайший путь из каждой вершины графа.

Алгоритм сравнивает все возможные пути между каждой парой вершин в графе. Это достигается за счет улучшения оценки кратчайшего пути до тех пор, пока оценка не станет оптимальной. Алгоритм в основном проверяет, находится ли вершина k на кратчайшем пути между вершинами i и j.

Рекурсия

Определим shortestPath(i,j,k) как длину кратчайшего пути между вершиной i и вершиной j, используя только вершины из множества {1,2,3,…,k-1,k} в качестве промежуточных точек. . Наша цель — найти длину кратчайшего пути между всеми вершинами i и j в V, используя вершины из V в качестве промежуточных точек.

Для каждой пары вершин i и j:

Кратчайший путь проходит через k, т. е. путь идет от i до k, а затем от k до j.
Кратчайший путь не проходит через k.

Следовательно, рекурсивная формула выглядит следующим образом:

Базовый вариант:
shortestPath(i,j,0)=graph(i,j)
Рекурсивный вариант:
shortestPath(i ,j,k)=min(кратчайшийПуть(i,j,k-1), кратчайшийПуть(i,k,k-1)+кратчайшийПуть(k,j,k-1))

Алгоритм использует природу динамического программирования для эффективного выполнения этой рекурсии.

Псевдокод:

floydWarshall(graph, V, E)
  minDistance[|V|][|V|]={inf} 
  // Initialising minDistance as the graph 
  for edge=0 upto |E| 
    u=edge.first 
    v=edge.second 
    minDistance[u][v]=graph[u][v]
 
  // Initialising minDistance for each vertex
  for vertex=0 upto |V| 
    minDistance[vertex][vertex]=0 
  for mid=0 upto |V| 
    for start=0 upto |V| 
      for dest=0 upto |V| 
        if minDistance[start][dest]>minDistance[start][mid]+minDistance[mid][dest] 
          minDistance[start][dest]=minDistance[start][mid]+minDistance[mid][dest] 
  return minDistance

Временная сложность: O(|V|3)

Проблема с отрицательным циклом

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

Однако для обнаружения отрицательных циклов можно использовать алгоритм Флойда-Уоршалла. Интуиция, стоящая за этим, заключается в том, что minDistance[v][v]=0 для любой вершины v, но если существует отрицательный цикл, выбор пути [v,….,C,….,v] уменьшит только кратчайший путь (где C — отрицательный цикл). Следовательно, если в графе существует отрицательный цикл, то в minDistance будет по крайней мере один отрицательный диагональный элемент.

Приложения

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

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

Спасибо, что прочитали статью!

Если у вас есть вопросы, оставьте комментарий ниже. Не забудьте поставить аплодисменты, если вам понравилась статья.