thexpot.net

Floyd-Warshall Algoritması, graf olarak ifade edilebilecek herhangi bir veri yapısında herhangi iki nokta arasındaki en kısa yolu bulmak için kullanılabilecek kodlaması oldukça basit bir algoritmadır. İnternette bu algoritmayı anlatan birçok kaynak bulabilirsiniz. Benim burada anlatacaklarım ise minimum teori ile maksimum pratik sunmak olacak. Pseudo kod yerine örnekler ve kod parçaları üzerinden açıklamaya çalışacağım. Floyd-Warshall algoritmasının özü çok basit bir formülden oluşuyor. A,B,C diye 3 tane noktamız olduğunu varsayalım. Bu durumda A ile C arasındaki en kısa mesafe min(mesafe(A,C), mesafe(A,B) + mesafe(B,C)) kadar olacaktır. Floyd-Warshall’ı uygulayabilmek için bir tabloya ihtiyacımız var. Bu tablonun boyutu nokta sayısına bağlı olarak belirlenecek. N tane noktamız var ise tablonun ebatları N*N olacaktır. Sağdaki örnek resme baktığımızda 5 nokta ve 5 kenardan oluşan bir graf görüyoruz. Bu grafdaki her bir kenar bitişikliği temsil ediyor. Bu durumda oluşturmamız gereken tablonun boyutu 5*5 olmalıdır.

int[,] table = new int[5,5];

Algoritmanın temelinde min fonksiyonu kullanıldığı için bu tablonun girdilerinin ilk değerleri maksimum olarak atıyoruz. Her bir noktanın kendine olan mesafesini 0, diğer noktalara olan mesafesini ise sonsuz kabul ederek başlayacağız.

int INFINITY = 9999999;
int N = 5;
for (int i = 0; i < N; i++)
  for(int j = 0; j < N; j++)
    table[i,j] = i == j ? 0 : INFINITY;

Bu işlemden sonra tablonun ilk değerleri aşağıdaki gibi olacaktır.

table	1	2	3	4	5
1	0	INF	INF	INF	INF
2	INF	0	INF	INF	INF
3	INF	INF	0	INF	INF
4	INF	INF	INF	0	INF
5	INF	INF	INF	INF	0

İkinci olarak noktalar arasındaki bağlantıları tutmak ve sorgulamak için bitişiklik matrisi oluşturmalıyız. Eğer bir noktadan diğerine bir kenar var ise tabloda o girdiye 1 değerini veriyoruz. Örneğin nokta 2′den nokta 3′e ve nokta 4′e birer kenar bulunuyor. Bundan dolayı tablomuzun [2,3] = [2,4] = 1 = [3,2] = [4,2]. Grafımız yönlü olmadığı için elde ettiğimiz bitişiklik matrisinin diyagonale göre simetrik olması gerekiyor. Çünkü 1′den 4′ e kenar varsa bu aynı zamanda 4′den 1′e de kenar var anlamına gelmektedir. Eğer örneğimiz yönlü bir graf olsaydı bunu söyleyemezdik. Bu işlemden sonra tablomuzun son hali aşağıdaki gibi olacak:

table	1	2	3	4	5
1	0	INF	INF	1	INF
2	INF	0	1	1	INF
3	INF	1	0	1	INF
4	1	1	1	0	1
5	INF	INF	INF	1	0

Simdi Floyd-Warshall formülünü uygulayabiliriz:

for( int k = 0; k < N; k++)
  for( int i = 0; i < N; i++)
    for( int j = 0; j < N; j++)
      table[i,j] = Math.Min(table[i,j], table[i,k] + table[k,j]);

Hepsi bu kadar. Bu işlemden sonra tablomuzun son hali şu şekilde olacak.

table	1	2	3	4	5
1	0	2	2	1	2
2	2	0	1	1	2
3	2	1	0	1	2
4	1	1	1	0	1
5	2	2	2	1	0

Artık tabloyu kullanarak her iki nokta arasındaki (a,b) en kısa mesafeyi sorgulayabiliriz. table[a,b] = table[b,a] Şimdi biraz koda yüklenelim ve daha değişik bir örnek üzerinde çalışalım. Farz edelim ki bize bir harita verilmiş ve A noktasından B noktasına en kısa mesafeyi bulmamız istenmiş olsun.

.......AXXXXXXX
..........X...X
.....XXXXXXXXXX
.....X........X
.XXXXXXXXXXXXXX
.X.....X..X....
.X.....X..X...X
.XXXXXXXXXXBXXX

X olan noktalar gidilebilecek yolu ifade etsin. Harita üzerindeki her bir karakteri yukarıdaki graftaki bir nokta olarak kabul edebiliriz. Bu durumda elimizde genişlik * yükseklik kadar nokta olacaktır. Her bir noktanın tablodaki yerini de (satır * genişlik) + sütun olarak belirleyebiliriz. Bitişiklik matrisini oluştururken her bir noktanın sağındaki, solundaki, üstündeki ve altındaki karakterlerin X,A,B karakterlerinden biri olup olmadığını kontrol etmek yeterli olacaktır. Eğer bu karakterlerden birisi ise kenar var diyeceğiz ve tabloya 1 değerini atayacağız. Örnek kod aşağıdaki gibi:

private readonly string[] map = new string[]
     {
        ".......AXXXXXXX",
        "..........X...X",
        ".....XXXXXXXXXX",
        ".....X........X",
        ".XXXXXXXXXXXXXX",
        ".X.....X...X..X",
        ".X.....X...X..X",
        ".XXXXXXXXXXBXXX",
     };

int findShortestPath()
{
  int width = map[0].Length;
  int height = map.Length;
  int N = width*height;
  int[,] table = new int[N,N];
  int INF = 9999999;

  //tablonun ilk değerlerini atıyoruz
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      table[i, j] = i == j ? 0 : INF;

  // bitişiklik matrisini oluşturuyoruz
  for (int i = 0; i < N; i++)
  {
    int row = i/width;
    int col = i%width;
    if (map[row][col] == '.') continue;
    // yapılabilecek tüm hareketler için olasıkları üretiyoruz
    // ve kontrol ediyoruz
    for (int dx = -1; dx <= 1; dx++)
      for (int dy = -1; dy <= 1; dy++)
      {
        // (1,1) (1,-1) gibi hareketler yapamıyoruz
        if (Math.Abs(dy) + Math.Abs(dx) == 2) continue;
        if (col + dx < width && col + dx >= 0 &&
            row + dy < height && row + dy >= 0)
        {
          char c = map[row + dy][col + dx];
          if (c == 'X' || c == 'A' || c == 'B')
          {
            int newindex = (row + dy)*width + col + dx;
            table[i, newindex] = table[newindex, i] = 1;
          }
        }
      }
    }

  for (int k = 0; k < N; k++)
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        table[i, j] = Math.Min(table[i, j], table[i, k] + table[k, j]);

  string joined = String.Join(String.Empty, map);
  int startIndex = joined.IndexOf('A');
  int endIndex = joined.IndexOf('B');
  return table[startIndex, endIndex];

}