Floyd - 1#974

Floyd - 1 (Editoryal)

Problem, tüm köşe çiftleri arasındaki en kısa mesafelerin bulunmasını gerektirmektedir. Bu, Floyd — Warshall algoritması ile çözülen klasik bir problemdir. Algoritma dinamik programlamaya dayanır ve grafın negatif ağırlıklı döngü içermemesi koşuluyla negatif kenar ağırlıklarıyla doğru şekilde çalışır. Bu koşul problemde garanti edilmektedir.

Algoritmanın fikri. Köşeleri $1$ 'den $n$ 'ye kadar numaralandıralım. $d_{k} [i] [j]$ d_k[i][j] ile, tüm ara köşeleri ${1, 2, \dots, k}$ \{1, 2, \ldots, k\} kümesine ait olan, $i$ köşesinden $j$ köşesine giden en kısa yolun uzunluğunu gösterelim. $k = 0$ k = 0 için ara köşe yoktur, dolayısıyla $d_{0} [i] [j]$ d_0[i][j], $i \to j$ i \to j kenarının ağırlığına eşittir, yani komşuluk matrisiyle çakışır.

Ara köşeleri ${1, \dots, k}$ \{1, \ldots, k\} arasında bulunan $i$ 'den $j$ 'ye en kısa yolu ele alalım. İki durum söz konusudur:

yol, $k$ köşesinden geçmez. Bu durumda uzunluğu $d_{k - 1} [i] [j]$ d_{k-1}[i][j]'ye eşittir;
yol, $k$ köşesinden geçer. Negatif ağırlıklı döngü olmadığından, $k$ köşesini tam olarak bir kez ziyaret etmek en uygunudur. Yol iki parçaya ayrılır: $i$ 'den $k$ 'ya ve $k$ 'dan $j$ 'ye. Her iki parçanın ara köşeleri de ${1, \dots, k - 1}$ \{1, \ldots, k - 1\} arasında yer alır, bu nedenle yolun uzunluğu $d_{k - 1} [i] [k] + d_{k - 1} [k] [j]$ d_{k-1}[i][k] + d_{k-1}[k][j]'ye eşittir.

İki seçenekten daha iyi olanını seçerek, şu yineleme bağıntısını elde ederiz:

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, gerekli olan en kısa mesafeleri içerir, çünkü grafın herhangi bir köşesi onda ara köşe olabilir.

Tek bir matriste hesaplama. Tüm $d_{0}, d_{1}, \dots, d_{n}$ d_0, d_1, \ldots, d_n matrislerini saklamaya gerek yoktur: tüm hesaplamalar doğrudan $g$ komşuluk matrisinde gerçekleştirilebilir. Gerçekten de, $k$ . adımda $g [i] [k]$ g[i][k] ve $g [k] [j]$ g[k][j] değerleri değişmez, çünkü $g [k] [k] = 0$ g[k][k] = 0'dır. Örneğin, $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]. Bu nedenle, matrisin diğer elemanlarının mevcut adımda zaten güncellenmiş olup olmaması önemli değildir.

Ara köşe $k$ üzerindeki döngünün en dıştaki döngü olması önemlidir: $k$ köşesi işlendiğinde, ara köşeleri ${1, \dots, k - 1}$ \{1, \ldots, k - 1\} kümesinden olan tüm mesafeler zaten hesaplanmış olmalıdır.

Karmaşıklık. Algoritma, her biri $n$ iterasyondan oluşan iç içe üç döngüden oluşur, dolayısıyla çalışma süresi $O (n^{3})$ O(n^3)'tür. $n \leq 100$ n \le 100 için bu, yaklaşık $1 0^{6}$ 10^6 işlem demektir.

Örnek

Örnekte verilen graf aşağıda gösterilmiştir. Graf tamdır, ancak $100$ ağırlıklı kenarlar şekilde gösterilmemiştir: aşağıda göreceğimiz gibi, bunların hiçbiri hiçbir en kısa yola ait değildir.

Algoritmayı simüle edelim. Başlangıç $g$ matrisi komşuluk matrisiyle çakışı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$ köşesinden başlayan yollar, $1$ köşesi üzerinden daha kısa hale gelir: $g [4] [2] = g [4] [1] + g [1] [2] = 4 + 5 = 9$ g[4][2] = g[4][1] + g[1][2] = 4 + 5 = 9 ve $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$ köşesi üzerinden, aşağıdaki yollar daha kısa hale gelir: $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 ve $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$ köşesinden geçmek hiçbir yolu kısaltmaz. Örneğin, $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$ köşesi üzerinden, $1$ ve $2$ köşelerine giden yollar daha kısa hale gelir: $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 ve $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 güncellemeye dikkat edin. $g [4] [2] = 9$ g[4][2] = 9 değeri $k = 1$ k = 1 adımında elde edilmiştir ve $4 \to 1 \to 2$ 4 \to 1 \to 2 yoluna karşılık gelir. Dolayısıyla, $g [3] [2] = 16$ g[3][2] = 16, iki ara köşeye sahip olan $3 \to 4 \to 1 \to 2$ 3 \to 4 \to 1 \to 2 yoluna karşılık gelir.

Son en kısa mesafe matrisi, örnekteki cevapla çakışı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$

Algoritmanın gerçeklenmesi

Grafın komşuluk matrisini $g$ dizisinde saklayalım.

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

floyd fonksiyonu, Floyd — Warshall algoritmasını gerçekler.

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

Programın ana bölümü. Girdi grafını okuyalım.

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

Floyd — Warshall algoritmasını çalıştıralım.

floyd();

Tüm köşe çiftleri arasındaki en kısa mesafeler matrisini yazdıralım.

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

Java gerçeklemesi

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 gerçeklemesi

floyd fonksiyonu, Floyd — Warshall algoritmasını gerçekler.

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]

Programın ana bölümü. Girdi grafını okuyalım.

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

Floyd — Warshall algoritmasını çalıştıralım.

floyd()

Tüm köşe çiftleri arasındaki en kısa mesafeler matrisini yazdıralım.

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