Coding Interview Prep · Урок

Флойд—Уоршелл: кратчайшие пути между всеми парами

Q: Урок «Флойд—Уоршелл: кратчайшие пути между всеми парами» бесплатный?

Да — полный текст урока «Флойд—Уоршелл: кратчайшие пути между всеми парами» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Q: Чему я научусь в уроке «Флойд—Уоршелл: кратчайшие пути между всеми парами»?

Заполните матрицу расстояний между всеми парами с помощью алгоритма Флойда—Уоршелла с тремя вложенными циклами и примените его для поиска минимального числа переходов между всеми парами вершин Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Q: Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Q: Сколько времени занимает урок «Флойд—Уоршелл: кратчайшие пути между всеми парами»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Q: Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

«Флойд—Уоршелл: кратчайшие пути между всеми парами» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Кратчайшие пути между всеми парами вершин

Алгоритм Флойда—Уоршелла вычисляет кратчайшие пути между каждой парой вершин взвешенного графа, в том числе графа с отрицательными весами рёбер (но без отрицательных циклов). Запуск алгоритма Дейкстры из каждого источника занимает O(V × (V+E) log V); алгоритм Флойда—Уоршелла работает за O(V³) независимо от плотности графа. Для плотных графов с V ≤ 500 алгоритм Флойда—Уоршелла часто проще и работает сопоставимо быстро.

Основная идея: промежуточные вершины

Идея алгоритма Флойда—Уоршелла такова: dp[i][j][k] = кратчайший путь из i в j, использующий только вершины {0, 1, ..., k} в качестве промежуточных. Кратчайший путь либо использует вершину k как промежуточную, либо нет. Если использует: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. Если нет: dp[i][j][k] = dp[i][j][k-1]. Поскольку третье измерение продвигается только вперёд, его можно устранить — обновлять значения на месте.

Инициализация матрицы расстояний

Начните с матрицы V×V: dist[i][i] = 0 (нулевое расстояние от вершины до самой себя), dist[i][j] = weight для прямых рёбер и dist[i][j] = inf для отсутствующих рёбер. Затем переберите все промежуточные вершины k, обновляя пары (i, j). Внешний цикл по k должен идти первым, чтобы корректно строить пути через постепенно расширяющееся множество разрешённых промежуточных вершин.

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w  # directed graph
    
    for k in range(V):       # intermediate node
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

Полная реализация с примером

Рассмотрим работу алгоритма Флойда—Уоршелла на графе из 4 вершин. После обработки каждой промежуточной вершины k в матрице появляются более короткие пути, проходящие через вершину k. Алгоритм естественным образом обрабатывает несколько переходов, постепенно строя кратчайшие пути.

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

V = 4
edges = [(0,1,3),(0,2,7),(1,2,1),(1,3,5),(2,3,2)]
dist = floyd_warshall(V, edges)
for row in dist:
    print([x if x != float('inf') else 'INF' for x in row])

Обнаружение отрицательных циклов

После выполнения алгоритма Флойда—Уоршелла проверьте главную диагональ: если для какого-либо dist[i][i] < 0, существует отрицательный цикл, проходящий через вершину i. Это происходит потому, что отрицательный цикл позволяет вернуться из i в i с отрицательной стоимостью. Если отрицательных циклов нет, все элементы диагонали остаются равными 0.

def has_negative_cycle_fw(V, edges):
    dist = floyd_warshall(V, edges)
    for i in range(V):
        if dist[i][i] < 0:
            return True  # negative cycle through node i
    return False

# Negative cycle: 0->1->2->0 with weights 1,-3,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-3),(2,0,1)]
print(has_negative_cycle_fw(3, edges_neg))  # True

Восстановление пути

Чтобы восстановить настоящий путь из i в j, поддерживайте матрицу next[i][j]: изначально для прямых рёбер установите next[i][j] = j. При обновлении через промежуточную вершину k устанавливайте next[i][j] = next[i][k]. Для восстановления пути начните с i и следуйте по указателям next, пока не достигнете j. Это добавляет O(V²) памяти и O(V) на восстановление каждого пути.

def fw_with_path(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    nxt = [[None]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w; nxt[u][v] = v
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt

def get_path(nxt, i, j):
    if nxt[i][j] is None: return []
    path = [i]
    while i != j:
        i = nxt[i][j]; path.append(i)
    return path

Транзитивное замыкание

Более простой вариант — транзитивное замыкание, отвечающее на вопрос «достижима ли вершина j из вершины i?» для всех пар вершин. Замените расстояния логическими значениями: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). Это алгоритм Флойда—Уоршелла с логической операцией OR вместо сложения и взятия минимума. Инициализируйте reach[i][i] = True и установите reach[i][j] = True для прямых рёбер.

def transitive_closure(V, edges):
    reach = [[False]*V for _ in range(V)]
    for i in range(V):
        reach[i][i] = True
    for u, v, _ in edges:
        reach[u][v] = True
    for k in range(V):
        for i in range(V):
            for j in range(V):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
    return reach

edges = [(0,1,1),(1,2,1)]
R = transitive_closure(3, edges)
print(R[0][2])  # True (0 can reach 2 via 0->1->2)

Сложность и выбор алгоритма

Алгоритм Флойда—Уоршелла: O(V³) времени и O(V²) памяти. Для плотных графов (E ≈ V²) с V ≤ 300 он быстрее, чем запуск алгоритма Дейкстры V раз (в этом случае также O(V³)). Для разреженного графа с V = 1000 и E = 3000 выполнение алгоритма Дейкстры из каждой вершины стоит O(V×E×log V) ≈ 33M, тогда как алгоритм Флойда—Уоршелла требует O(V³) = 10⁹ операций — здесь выигрывает алгоритм Дейкстры. Важно понимать, когда уместен каждый из алгоритмов.

Минимальное число переходов между всеми парами

Задайте всем рёбрам вес 1 (или используйте булеву матрицу смежности с алгоритмом Флойда—Уоршелла, заменив операцию минимума сложением): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Это вычисляет минимальное число переходов между всеми парами — результат BFS для всех пар, полученный за один проход алгоритма Флойда—Уоршелла за O(V³).

def min_hops_all_pairs(V, adj_list):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
        for j in adj_list[i]:
            dist[i][j] = 1
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

adj = [[1,2],[2],[3],[],[]]
print(min_hops_all_pairs(5, adj)[0])  # [0, 1, 1, 2, INF]

Контекст собеседования: когда интервьюеры спрашивают об алгоритме Флойда—Уоршелла

Алгоритм Флойда—Уоршелла встречается на собеседованиях в задачах, связанных с: (1) расстояниями между всеми парами вершин небольшого графа, (2) проверкой существования цикла с отрицательным суммарным весом, (3) вычислением кратчайших путей в задачах распространения ограничений и (4) задачами, явно требующими решений за O(V³), где V ≤ 200. Всегда упоминайте структуру из трёх циклов и требование отсутствия отрицательных циклов для корректности.

Неориентированные графы с алгоритмом Флойда—Уоршелла

Для неориентированных графов добавьте оба направления для каждого ребра: dist[u][v] = dist[v][u] = weight. Остальная часть алгоритма не меняется. Полученная матрица симметрична: dist[i][j] == dist[j][i] для всех пар. При инициализации будьте внимательны и не присваивайте рёбрам только одно направление — неориентированные рёбра необходимо добавить в обоих направлениях в начальную матрицу до запуска трёх циклов.

def fw_undirected(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w  # both directions for undirected
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Быстрая проверка

Проверьте своё понимание концепций курса «Структуры данных и алгоритмы — подготовка к техническому собеседованию», рассмотренных в этом уроке.

Итоги урока

В этом уроке Вы узнали: алгоритм Флойда—Уоршелла вычисляет кратчайшие пути между всеми парами с помощью трёх вложенных циклов и рекуррентного соотношения dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), отрицательные циклы можно обнаружить, проверив, что после завершения алгоритма существует dist[i][i] < 0, а алгоритм работает за O(V³) времени и использует O(V²) памяти. Далее мы снова рассмотрим применение алгоритмов поиска кратчайших путей на примере задачи «Задержка в сети» и методы восстановления пути.

Часто задаваемые вопросы

Урок «Флойд—Уоршелл: кратчайшие пути между всеми парами» бесплатный?

Да — полный текст урока «Флойд—Уоршелл: кратчайшие пути между всеми парами» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Флойд—Уоршелл: кратчайшие пути между всеми парами»?

Заполните матрицу расстояний между всеми парами с помощью алгоритма Флойда—Уоршелла с тремя вложенными циклами и примените его для поиска минимального числа переходов между всеми парами вершин Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Флойд—Уоршелл: кратчайшие пути между всеми парами»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

Алгоритм Дейкстры с очередью с приоритетами
Беллман—Форд и отрицательные циклы
Флойд—Уоршелл: кратчайшие пути между всеми парами
Задержка в сети и восстановление пути

← Назад к Coding Interview Prep