Флойд - 1#974

Флойд - 1 (Розбір)

У задачі потрібно знайти найкоротші відстані між усіма парами вершин. Це класична задача, яка розв'язується алгоритмом Флойда — Уоршелла. Алгоритм ґрунтується на динамічному програмуванні та коректно працює з ребрами від'ємної ваги за умови, що граф не містить циклів від'ємної ваги. Ця умова гарантована в задачі.

Ідея алгоритму. Пронумеруємо вершини від $1$ до $n$ . Позначимо через $d_{k} [i] [j]$ d_k[i][j] довжину найкоротшого шляху з вершини $i$ до вершини $j$ , усі проміжні вершини якого належать множині ${1, 2, \dots, k}$ \{1, 2, \ldots, k\}. При $k = 0$ k = 0 проміжних вершин немає, тому $d_{0} [i] [j]$ d_0[i][j] дорівнює вазі ребра $i \to j$ i \to j, тобто збігається з матрицею суміжності.

Розглянемо найкоротший шлях з $i$ до $j$ , проміжні вершини якого лежать серед ${1, \dots, k}$ \{1, \ldots, k\}. Можливі два випадки:

шлях не проходить через вершину $k$ . Тоді його довжина дорівнює $d_{k - 1} [i] [j]$ d_{k-1}[i][j];
шлях проходить через вершину $k$ . Оскільки циклів від'ємної ваги немає, оптимально відвідати вершину $k$ рівно один раз. Шлях розбивається на дві частини: від $i$ до $k$ і від $k$ до $j$ . Проміжні вершини обох частин лежать серед ${1, \dots, k - 1}$ \{1, \ldots, k - 1\}, тому довжина шляху дорівнює $d_{k - 1} [i] [k] + d_{k - 1} [k] [j]$ d_{k-1}[i][k] + d_{k-1}[k][j].

Обираючи кращий з двох варіантів, отримуємо рекурентне співвідношення:

d_{k} [i] [j] = min (d_{k - 1} [i] [j], d_{k - 1} [i] [k] + d_{k - 1} [k] [j])

d_k[i][j] = \min(d_{k-1}[i][j], d_{k-1}[i][k] + d_{k-1}[k][j])

Матриця $d_{n}$ d_n містить потрібні найкоротші відстані, оскільки в ній проміжною може бути будь-яка вершина графа.

Обчислення в одній матриці. Немає потреби зберігати всі матриці $d_{0}, d_{1}, \dots, d_{n}$ d_0, d_1, \ldots, d_n: усі обчислення можна виконувати безпосередньо в матриці суміжності $g$ . Справді, на кроці $k$ значення $g [i] [k]$ g[i][k] та $g [k] [j]$ g[k][j] не змінюються, оскільки $g [k] [k] = 0$ g[k][k] = 0. Наприклад, $g [i] [k] = min (g [i] [k], g [i] [k] + g [k] [k]) = g [i] [k]$ g[i][k] = \min(g[i][k], g[i][k] + g[k][k]) = g[i][k]. Тому не має значення, чи вже оновлено інші елементи матриці на поточному кроці.

Важливо, щоб цикл за проміжною вершиною $k$ був зовнішнім: на момент обробки вершини $k$ усі відстані з проміжними вершинами з ${1, \dots, k - 1}$ \{1, \ldots, k - 1\} мають бути вже обчислені.

Складність. Алгоритм складається з трьох вкладених циклів по $n$ ітерацій кожен, тому час його роботи становить $O (n^{3})$ O(n^3). Для $n \leq 100$ n \le 100 це близько $1 0^{6}$ 10^6 операцій.

Приклад

Граф, наведений у прикладі, зображено нижче. Граф повний, але ребра ваги $100$ на малюнку не показані: як ми побачимо далі, жодне з них не належить жодному найкоротшому шляху.

Просимулюємо роботу алгоритму. Початкова матриця $g$ збігається з матрицею суміжності:

	$1$	$2$	$3$	$4$
$1$	$0$	$5$	$9$	$100$
$2$	$100$	$0$	$2$	$8$
$3$	$100$	$100$	$0$	$7$
$4$	$4$	$100$	$100$	$0$

$k = 1$ \boldsymbol{k = 1}. Шляхи з вершини $4$ стають коротшими через вершину $1$ : $g [4] [2] = g [4] [1] + g [1] [2] = 4 + 5 = 9$ g[4][2] = g[4][1] + g[1][2] = 4 + 5 = 9 та $g [4] [3] = g [4] [1] + g [1] [3] = 4 + 9 = 13$ g[4][3] = g[4][1] + g[1][3] = 4 + 9 = 13.

$k = 2$ \boldsymbol{k = 2}. Через вершину $2$ стають коротшими такі шляхи: $g [1] [3] = g [1] [2] + g [2] [3] = 5 + 2 = 7$ g[1][3] = g[1][2] + g[2][3] = 5 + 2 = 7, $g [1] [4] = g [1] [2] + g [2] [4] = 5 + 8 = 13$ g[1][4] = g[1][2] + g[2][4] = 5 + 8 = 13 та $g [4] [3] = g [4] [2] + g [2] [3] = 9 + 2 = 11$ g[4][3] = g[4][2] + g[2][3] = 9 + 2 = 11.

$k = 3$ \boldsymbol{k = 3}. Проходження через вершину $3$ не скорочує жодного шляху. Наприклад, $g [1] [3] + g [3] [4] = 7 + 7 = 14 > g [1] [4] = 13$ g[1][3] + g[3][4] = 7 + 7 = 14 > g[1][4] = 13.

$k = 4$ \boldsymbol{k = 4}. Через вершину $4$ стають коротшими шляхи до вершин $1$ та $2$ : $g [2] [1] = g [2] [4] + g [4] [1] = 8 + 4 = 12$ g[2][1] = g[2][4] + g[4][1] = 8 + 4 = 12, $g [3] [1] = g [3] [4] + g [4] [1] = 7 + 4 = 11$ g[3][1] = g[3][4] + g[4][1] = 7 + 4 = 11 та $g [3] [2] = g [3] [4] + g [4] [2] = 7 + 9 = 16$ g[3][2] = g[3][4] + g[4][2] = 7 + 9 = 16.

Зверніть увагу на останнє оновлення. Значення $g [4] [2] = 9$ g[4][2] = 9 було отримано на кроці $k = 1$ k = 1 і відповідає шляху $4 \to 1 \to 2$ 4 \to 1 \to 2. Тому $g [3] [2] = 16$ g[3][2] = 16 відповідає шляху $3 \to 4 \to 1 \to 2$ 3 \to 4 \to 1 \to 2, який має дві проміжні вершини.

Остаточна матриця найкоротших відстаней збігається з відповіддю з прикладу:

	$1$	$2$	$3$	$4$
$1$	$0$	$5$	$7$	$13$
$2$	$12$	$0$	$2$	$8$
$3$	$11$	$16$	$0$	$7$
$4$	$4$	$9$	$11$	$0$

Реалізація алгоритму

Збережемо матрицю суміжності графа в масиві $g$ .

#define MAX 101
int g[MAX][MAX];

Функція floyd реалізує алгоритм Флойда — Уоршелла.

void floyd(void)
{
  int i, j, k;
  for(k = 0; k < n; k++)
  for(i = 0; i < n; i++)
  for(j = 0; j < n; j++)
    if (g[i][k] + g[k][j] < g[i][j]) g[i][j] = g[i][k] + g[k][j];
}

C++

Основна частина програми. Зчитаємо вхідний граф.

scanf("%d",&n);
for(i = 0; i <  n; i++)
for(j = 0; j <  n; j++)
  scanf("%d",&g[i][j]);

Запустимо алгоритм Флойда — Уоршелла.

floyd();

Виведемо матрицю найкоротших відстаней між усіма парами вершин.

for(i = 0; i <  n; i++)
{
  for(j = 0; j <  n; j++)
    printf("%d ",g[i][j]);
  printf("\n");
}

Реалізація на Java

import java.util.*;

public class Main 
{
  static int g[][];
  static int n;
  
  static void floyd()
  {
    for(int k = 0; k < n; k++)
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      if (g[i][k] + g[k][j] < g[i][j]) 
        g[i][j] = g[i][k] + g[k][j];
  }
  
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);	  
    n = con.nextInt();
    g = new int[n][n];

    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      g[i][j] = con.nextInt();

    floyd();

    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < n; j++)
    	  System.out.print(g[i][j] + " ");
      System.out.println();
    }
    con.close();
  }
}

Java

Реалізація на Python

Функція floyd реалізує алгоритм Флойда — Уоршелла.

def floyd():
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if g[i][k] + g[k][j] < g[i][j]:
           g[i][j] = g[i][k] + g[k][j]

Основна частина програми. Зчитаємо вхідний граф.

n = int(input())
g = [[] for _ in range(n)]
for i in range(n):
  g[i] = list(map(int, input().split()))

Запустимо алгоритм Флойда — Уоршелла.

floyd()

Виведемо матрицю найкоротших відстаней між усіма парами вершин.

for i in range(n):
  print(*g[i])