Elimizde aşağıdaki gibi bir grafik olsun.Her bir node'un diğer tüm node'lara olan en kısa yolunu hesaplamak istiyorsak Floyd Warshall methodunu kullanırız.
D(0) matrisindeki tüm a x b elemanları a'dan b'ye olan mesafeyi gösterir.Gerekli işlemleri uygulayarak tüm a x b elemanları için a'dan b'ye olan en kısa mesafeleri bulacağız.
π matrix'inde tanımsız olan yerlere ve çarprazlama yerlere (a x a) NIL yazarız.Kalan yerlere row numarasını yazarız.Böylece π(0) matrixini buluruz.Bundan sonraki adımlarda D matrixlerinin elemanlarında meydana gelen bir güncelleme,kaçıncı adımda yapıldıysa bu adımın numarası π(0) matrixindeki aynı pozisyona yazılır.
D(0) matrix'inde ilk satırı nasıl bulduğumuzu anlatalım:
Yukarıdaki grafiğe bakalım.
1 numaralı node'dan çıkan node'lara bakarak 1.satırı yazalım.
1 x 1 = 0
1 x 2 = 3 1 numaralı node'un 2 numaralı node'a doğru olan directed edge'inin weight'i "3".
1 x 3 = 8 1 numaralı node'un 3 numaralı node'a doğru olan directed edge'inin weight'i "8".
1 x 4 = ∞ 1 numaralı node'dan 4 numaralı node'a doğru bir directed edge yok o yüzden "∞(sonsuz)" dedik.
1 x 5 = -4 1 numaralı node'un 5 numaralı node'a doğru olan directed edge'inin weight'i "-4".
Böylece D(0) ve π(0) matrixlerini bulduk.5 tane node'umuz olduğu için 5 x 5 lik matrix 'lerle çalışıyoruz ve 5 adımda D(5) VE π(5) 'i bularak tüm kısa yolları elde etmiş olacağız.
1.adım: D(1) ve π(1) ' i bulalım.
D(0) matrix'inde 1. satırın ve 1. sütunun tümünü yuvarlak içine alalım.Şimdi bu yuvarlaktaki bir satırı ve bir sütunu ele alalım ve toplayalım buna karşılık gelen pozisyondaki elemandan daha küçük bir sayı elde ettiysek bunu oraya yazalım.Açıklayalım:
1.sütunda ;
2.satırda ∞ var dolayısıyla 2.satırdaki hiçbir sayı değişmez.
3.satırda ∞ var dolayısıyla 3.satırdaki hiçbir sayı değişmez.
4.satırda 2 var.
1.satırda ;
2.sütunda 3 var. 2 + 3 = 5 5 < ∞ olduğu için 4 x 2 deki ∞
elemanını siler yerine 5 yazarız. Şu anda 1.satır ve sütunları
incelediğimiz için ve D matrixinde 4 x 2 de değişiklik yaptığımız için π
matrixinde 4 x 2 deki elemanı "1" ile değişitiririz.
3.sütunda 8 var. 2 + 8 = 10 10 > -5 olduğu için değişiklik yapmayız. Toplama
sonucunda daha küçük bir sayı bulursak değişiklik yapıyoruz.Unutmayın ki
amacımız en kısa mesafeyi bulmak!
4.sütunda ∞ var. Dolayısıyla değişiklik yapılamaz.
5.sütunda -4 var. 2 + (-4) = -2 -2 < ∞ olduğu için 4 x 5 deki
∞ elemanını siler yerine -2 yazarız. Şu anda 1.satır ve sütunları
incelediğimiz için ve D matrixinde 4 x 5 de değişiklik yaptığımız için π
matrixinde 4 x 5 deki elemanı "1" ile değiştiririz.
5.satırda ∞ var dolayısıyla 2.satırdaki hiçbir sayı değişmez.
Bu değişiklikler sonunda elde ettiğimiz matrixler D(1) ve π(1) 'dir.
2.adım: D(2) ve π(2) ' i bulalım. Bu kısmı atlıyorum(Benzer şekilde kendiniz yapabilirsiniz.)
3.adım: D(3) ve π(3) ' i bulalım. Bu kısmı da atlıyorum.(Benzer şekilde kendiniz yapabilirsiniz.)
4.adım: D(4) ve π(4) ' i bulalım.
D(3) matrix'inde 4. satırın ve 4. sütunun tümünü yuvarlak içine alalım.Şimdi bu yuvarlaktaki bir satırı ve bir sütunu ele alalım ve toplayalım buna karşılık gelen pozisyondaki elemandan daha küçük bir sayı elde ettiysek bunu oraya yazalım.Açıklayalım:
4.sütunda ;
1.satırda 4 var.
4.satırda ;
1.sütunda 2 var. 4 + 2 = 6 6 > 0 olduğu için değişiklik yapmayız.
2.sütunda -1 var. 4 + (-1) = 3 3 =3 olduğu için değişiklik yapmayız.
3.sütunda -5 var. 4 + (-5) = -1 -1 < 8 olduğu için 1 x 3 deki
8 elemanını siler yerine -1 yazarız. Şu anda 4.satır ve sütunları
incelediğimiz için ve D matrixinde 1 x 3 de değişiklik yaptığımız için π
matrixinde 1 x 3 deki elemanı "4" ile değiştiririz.
5.sütunda -2 var. 4 + (-2) = 2 2 > -4 olduğu için değişiklik yapmayız.
2.satırda 1 var.
4.satırda ;
1.sütunda 2 var. 1 + 2 = 3 3 < ∞ olduğu için 2 x 1 deki
∞ elemanını siler yerine 3 yazarız. Şu anda 4.satır ve sütunları
incelediğimiz için ve D matrixinde 2 x 1 de değişiklik yaptığımız için π
matrixinde 2 x 1 deki elemanı "4" ile değiştiririz.
2.sütunda -1 var. 1 + (-1) = 0 0 =0 olduğu için değişiklik yapmayız.
3.sütunda -5 var. 1 + (-5) = -4 -4 < ∞ olduğu için 2 x 3 deki
∞ elemanını siler yerine -4 yazarız. Şu anda 4.satır ve sütunları
incelediğimiz için ve D matrixinde 2 x 3 de değişiklik yaptığımız için π
matrixinde 2 x 3 deki elemanı "4" ile değiştiririz.
5.sütunda -2 var. 1 + (-2) = -1 -1 < 7 olduğu için 2 x 5 deki
7 elemanını siler yerine -1 yazarız. Şu anda 4.satır ve sütunları
incelediğimiz için ve D matrixinde 2 x 5 de değişiklik yaptığımız için π
matrixinde 2 x 5 deki elemanı "4" ile değiştiririz.
3.satırda 5 var.
4.satırda ;
1.sütunda 2 var. 5 + 2 = 7 7 < ∞ olduğu için 3 x 1 deki ∞
elemanını siler yerine 7 yazarız. Şu anda 4.satır ve sütunları
incelediğimiz için ve D matrixinde 3 x 1 de değişiklik yaptığımız için π
matrixinde 3 x 1 deki elemanı "4" ile değişitiririz.
2.sütunda -1 var. 5 + -1 = 4 4 = 4 olduğu için değişiklik yapmayız.
3.sütunda -5 var. 5 + (-5) = 0 0 = 0 olduğu için değişiklik yapmayız.
5.sütunda -2 var. 5 + (-2) = 3 3 < 11 olduğu için 3 x 5 deki
11 elemanını siler yerine 3 yazarız. Şu anda 4.satır ve sütunları
incelediğimiz için ve D matrixinde 3 x 5 de değişiklik yaptığımız için π
matrixinde 3 x 5 deki elemanı "4" ile değiştiririz.
5.satırda 6 var.
4.satırda ;
1.sütunda 2 var. 5 + 2 = 7 7 < ∞ olduğu için değişiklik yapmayız.
2.sütunda -1 var. 5 + -1 = 4 4 = 4 olduğu için değişiklik yapmayız.
3.sütunda -5 var. 5 + (-5) = 0 0 = 0 olduğu için değişiklik yapmayız.
5.sütunda -2 var. 6 + (-2) = 4 4 > 0 olduğu için değişiklik yapmayız.
Bu değişiklikler sonunda elde ettiğimiz matrixler D(1) ve π(1) 'dir.
5.adım: D(5) ve π(5) ' i bulalım. Bu kısmı da atlıyorum.(Benzer şekilde kendiniz yapabilirsiniz.)
Daha fazlası için:
1- Şu linkten farklı bir örneğe ulaşabilirsiniz: http://esor.ie.dal.ca/files/Supplemental%20Problems/05a%20All%20shortest%20paths,%20Floyd-Warshall.pdf
Kırılma ihtimaline karşı aynı pdf'e buradan da ulaşabilirsiniz: (Açılan sayfada en üstte şöyle yazan yere basın: İndir: )
Hiç yorum yok:
Yorum Gönder