Floyd - 1#974

Floyd - 1 (Həll təhlili)

Məsələ bütün təpə cütləri arasında ən qısa məsafələrin tapılmasını tələb edir. Bu, Floyd — Warshall alqoritmi ilə həll olunan klassik məsələdir. Alqoritm dinamik proqramlaşdırmaya əsaslanır və qrafda mənfi çəkili tsikl olmadığı şərtlə mənfi kənar çəkiləri ilə düzgün işləyir. Bu şərt məsələdə təmin olunur.

Alqoritmin ideyası. Təpələri $1$ -dən $n$ -ə qədər nömrələyək. $d_{k} [i] [j]$ d_k[i][j] ilə $i$ təpəsindən $j$ təpəsinə qədər olan, bütün aralıq təpələri ${1, 2, \dots, k}$ \{1, 2, \ldots, k\} çoxluğuna aid olan ən qısa yolun uzunluğunu işarə edək. $k = 0$ k = 0 üçün aralıq təpələr yoxdur, ona görə $d_{0} [i] [j]$ d_0[i][j] $i \to j$ i \to j kənarının çəkisinə bərabərdir, yəni qonşuluq matrisi ilə üst-üstə düşür.

$i$ -dən $j$ -yə, aralıq təpələri ${1, \dots, k}$ \{1, \ldots, k\} çoxluğunda yerləşən ən qısa yolu nəzərdən keçirək. İki hal mümkündür:

yol $k$ təpəsindən keçmir. Onda onun uzunluğu $d_{k - 1} [i] [j]$ d_{k-1}[i][j]-ə bərabərdir;
yol $k$ təpəsindən keçir. Mənfi çəkili tsikl olmadığı üçün $k$ təpəsini dəqiq bir dəfə ziyarət etmək optimaldır. Yol iki hissəyə bölünür: $i$ -dən $k$ -ya və $k$ -dan $j$ -yə. Hər iki hissənin aralıq təpələri ${1, \dots, k - 1}$ \{1, \ldots, k - 1\} çoxluğunda yerləşir, ona görə yolun uzunluğu $d_{k - 1} [i] [k] + d_{k - 1} [k] [j]$ d_{k-1}[i][k] + d_{k-1}[k][j]-ə bərabərdir.

İki variantdan daha yaxşısını seçərək, aşağıdakı rekurrent münasibəti alırıq:

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 matrisi tələb olunan ən qısa məsafələri ehtiva edir, çünki qrafın istənilən təpəsi onda aralıq təpə ola bilər.

Tək matrisdə hesablama. Bütün $d_{0}, d_{1}, \dots, d_{n}$ d_0, d_1, \ldots, d_n matrislərini saxlamağa ehtiyac yoxdur: bütün hesablamaları birbaşa qonşuluq matrisi $g$ -də yerinə yetirmək olar. Həqiqətən, $k$ addımında $g [i] [k]$ g[i][k] və $g [k] [j]$ g[k][j] qiymətləri dəyişmir, çünki $g [k] [k] = 0$ g[k][k] = 0. Məsələn, $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]. Ona görə də cari addımda matrisin digər elementlərinin artıq yenilənib-yenilənməməsinin əhəmiyyəti yoxdur.

Vacibdir ki, aralıq təpə $k$ üzrə dövr xarici dövr olsun: $k$ təpəsi emal olunana qədər, aralıq təpələri ${1, \dots, k - 1}$ \{1, \ldots, k - 1\} çoxluğundan olan bütün məsafələr artıq hesablanmış olmalıdır.

Mürəkkəblik. Alqoritm hər biri $n$ təkrardan ibarət üç iç-içə dövrdən ibarətdir, ona görə işləmə vaxtı $O (n^{3})$ O(n^3)-dir. $n \leq 100$ n \le 100 üçün bu təxminən $1 0^{6}$ 10^6 əməliyyatdır.

Misal

Misalda verilən qraf aşağıda göstərilib. Qraf tamdır, lakin çəkisi $100$ olan kənarlar şəkildə göstərilməyib: aşağıda görəcəyimiz kimi, onlardan heç biri heç bir ən qısa yola daxil olmur.

Alqoritmi simulyasiya edək. İlkin $g$ matrisi qonşuluq matrisi ilə üst-üstə düşür:

	$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$ təpəsindən yollar $1$ təpəsi vasitəsilə qısalır: $g [4] [2] = g [4] [1] + g [1] [2] = 4 + 5 = 9$ g[4][2] = g[4][1] + g[1][2] = 4 + 5 = 9 və $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$ təpəsi vasitəsilə aşağıdakı yollar qısalır: $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 və $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$ təpəsindən keçmək heç bir yolu qısaltmır. Məsələn, $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$ təpəsi vasitəsilə $1$ və $2$ təpələrinə yollar qısalır: $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 və $g [3] [2] = g [3] [4] + g [4] [2] = 7 + 9 = 16$ g[3][2] = g[3][4] + g[4][2] = 7 + 9 = 16.

Son yeniləməyə diqqət edin. $g [4] [2] = 9$ g[4][2] = 9 qiyməti $k = 1$ k = 1 addımında alınıb və $4 \to 1 \to 2$ 4 \to 1 \to 2 yoluna uyğun gəlir. Buna görə, $g [3] [2] = 16$ g[3][2] = 16 iki aralıq təpəsi olan $3 \to 4 \to 1 \to 2$ 3 \to 4 \to 1 \to 2 yoluna uyğun gəlir.

Son ən qısa məsafələr matrisi misaldakı cavabla üst-üstə düşür:

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

Alqoritmin realizasiyası

Qrafın qonşuluq matrisini $g$ massivində saxlayın.

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

floyd funksiyası Floyd — Warshall alqoritmini realizə edir.

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++

Proqramın əsas hissəsi. Daxil olan qrafı oxuyuruq.

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

Floyd — Warshall alqoritmini işə salırıq.

floyd();

Bütün təpə cütləri arasında ən qısa məsafələr matrisini çap edirik.

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

Java realizasiyası

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 realizasiyası

floyd funksiyası Floyd — Warshall alqoritmini realizə edir.

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]

Proqramın əsas hissəsi. Daxil olan qrafı oxuyuruq.

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

Floyd — Warshall alqoritmini işə salırıq.

floyd()

Bütün təpə cütləri arasında ən qısa məsafələr matrisini çap edirik.

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