gokhanca

En Kısa Yol probleminde, ulaştırma şebekesindeki Kaynak ile Varış Noktası arasındaki en kısa bulunmaya çalışılır. Amaç, şebeke üzerindeki iki düğüm noktası arasındaki en kısa uzunluğu ve rotayı bulmaktır.

Mesela karayolları haritası üzerinde seçilen iki şehir arasındaki en kısa gidiş rotasını bulmak gibi. Günlük hayatta ve özellikle Mühendislik Uygulamalarında sıkça karşılaşılan bir problemdir.

Öncelikle problemde geçen bazı tanımları yapalım.

"Düğüm Noktası", gidilecek hedef, bulunulan nokta, geçilen bölüm ..gibi şebeke üzerindeki tanımlanmış bölgeleri gösterir. Mesela Karayolları haritası için şehir, ilçe, köy gibi yerleşim birimleri düğüm noktasıdır.

"Bağlantı", iki düğüm noktası arasındaki direkt ilişkiyi gösterir. Mesela iki şehir direkt birbirine bağlı mıdır? Bağlantıların iki türü vardır. Yönlü ve Yönsüz Bağlantılar. Yönlü bağlantılar, şebeke üzerinde ilerlerken bizi etkiler. Gidişin tek tarafa olduğu birleşmeleri gösterir. Mesela aşağıdaki şebekede 2'den 1'e gidiş vardır. ama 1'den 2'ye gidiş yoktur. Buna yönlü bağlantı denir. Yönsüz bağlantı ise her iki yönde de birleşmenin söz konusu olduğu durumlarda kullanılır. Her bağlantının bir değeri vardır. Mesela iki şehir arasındaki (km) uzaklık.

Bağlantılar bağıntı ifadesi olarak tanımlanırlar. Bunu, "( KaynakDüğüm , HedefDüğüm ) = BağlantıDeğeri" olarak belirtiriz.
( 1 , 2 ) = 0
( 2 , 1 ) = 40
( 2 , 5 ) = 23 ..gibi.

 

 

"Rota", şebeke üzerindeki gidiş yolunu veren bilgidir. Mesela örnekte 1'den 2'ye gidebilmek için 1 -> 3 -> 5 -> 2 rotası 1 ile 2 arasındaki en kısa yoldur. Bu rotanın değeri ( 6+2+23 = 31) 'dir.

 

İki tür En Kısa Yol Algoritması vardır. Dijksta ve Floyd Yöntemi.

 

1. DIJKSTRA ALGORÄ°TMASI :

Bu algoritmada her düğüm için etiket verilir. Bu etiketler "Geçici" ve "Kalıcı" olarak değer alırlar. Daha iyi bir yol bulunana kadar etiket değeri "Geçici"dir. Eğer en iyi yol bulunmuşsa etiket "Kalıcı"ya dönüştürülür. Bu algoritma sadece, seçilen iki düğüm noktası arasındaki en kısa yolu verir. Algoritmanın adımları aşağıdaki gibidir.

0. Adım : Kaynak Düğümünü "Kalıcı" olarak etiketle. Adım Sayısı "i" 'yi 1 yap.

i. Adım : j'nin "Kalıcı" etiketlenmemiş olması şartıyla, i düğümünden ulaşılabilen her j düğümü için geçici mesafeleri hesapla. Eğer j düğümü başka bir k düğümü ile zaten etiketlenmişse ve daha iyi bir i,j bağlantısı bulunuyorsa j,k bağlantısını i,j bağlantısı ile değiştir. Tüm düğümlerde "Kalıcı" etiketi varsa dur. Aksi halde tüm "Geçici" etiketleri arasından en kısa mesafeli bağlantıyı seç ve i. adımı tekrarla.

Örnek:

 

0. yineleme : "Kalıcı" etiket [ 0, - ]'yi 1. düğüme ata.

1. yineleme : 2. ve 3. düğümlere ( en son "Kalıcı" olarak etiketlenen) 1. düğümden ulaşılabilir. Böylece etiketlenen düğümlerin "Geçici" ve "Kalıcı" listesi aşağıdaki gibi olur.

 

Düğüm	Etiket	Durum
1	[ 0 , - ]	Kalıcı
2	[ 0 + 100 , 1 ] = [ 100 , 1 ]	Geçici
3	[ 0 + 30 , 1 ] = [ 30 , 1 ]	Geçici

 

2. ve 3. düğümün etiketleri olan iki geçici etiketten [ 100 , 1 ] ve [ 30 , 1 ]'e bakıldığında, 3. düğümün daha kısa uzaklığı verdiği görülür. Dolayısıyla 3. düğümün etiketi "Kalıcı" olarak değiştirilir.

 

Düğüm	Etiket	Durum
1	[ 0 , - ]	Kalıcı
2	[ 100 , 1 ]	Geçici
3	[ 30 , 1 ]	Kalıcı

 

2. yineleme : 4. ve 5. düğümlere 3. düğümden ulaşılabilir ve etiketlenen düğümlerin listesi aşağıdaki gibi oluşur.

 

Düğüm	Etiket	Durum
1	[ 0 , - ]	Kalıcı
2	[ 100 , 1 ]	Geçici
3	[ 30 , 1 ]	Kalıcı
4	[ 30 + 10 , 3 ] = [ 40 , 3 ]	Geçici
5	[ 30 + 60 , 3 ] = [ 90 , 3 ]	Geçici

 

3. düğümdeki [ 40, 3 ] geçici etiketinin durumu "Kalıcı" olarak değiştirilir.

 

Düğüm	Etiket	Durum
1	[ 0 , - ]	Kalıcı
2	[ 100 , 1 ]	Geçici
3	[ 30 , 1 ]	Kalıcı
4	[ 40 , 3 ]	Kalıcı
5	[ 90 , 3 ]	Geçici

 

3. yineleme : 2. ve 5. düğümlere 4. düğümden ulaşılabilir. Böylece etiketlenmiş düğümlerin listesi aşağıdaki gibi olur.

 

Düğüm	Etiket	Durum
1	[ 0 , - ]	Kalıcı
2	[ 40 + 15 , 4 ] = [ 55 , 4 ]	Geçici
3	[ 30 , 1 ]	Kalıcı
4	[ 40 , 3 ]	Kalıcı
5	[ 90 , 3 ] veya [ 40 + 50 , 4 ] = [ 90 , 4 ]	Geçici

 

2. yinelemede 2. düğümün geçici etiketi [ 100 , 1 ], 3, yinelemede 4. düğüm için daha kısa bir yol bulunduğunu gösterdiğinden [ 55 , 4 ] olarak değiştirilir. Ayrıca 3. yinelemede 5. düğümün aynı uzaklığa sahip iki alternatifi vardır.

 

4. yineleme : 2. düğümden sadece 3. düğüme ulaşılabilir. Bununla birlikte 3. düğüm "Kalıcı" olarak etiketlendiğinden yeniden etiketlenmez. Etiketlerin yeni listesi 3. yinelemede 2. düğümdeki etiketin kalıcı olması dışında aynı kalır. Bu da 5. düğümü tek "Geçici" etiket olarak bırakır. 5. düğüm diğer düğümlere gitmediğinden statüsü "Kalıcı"ya dönüştürülür ve süreç tamamlanır.

 

 

1. düğüm ile şebekedeki başka bir düğüm arasındaki en kısa yolu belirlemek için, istenilen varış düğümünden başlanır ve "Kalıcı" etiketlerin verdiği bilgi kullanılarak düğümlerden geriye doğru gidilir. Örneğin 1. düğümden 2. düğüme en kısa yolu aşağıdaki sıra belirler.

(2) --> [ 55 , 4] --> (4) --> [ 40 , 3] --> (3) --> [ 30 , 1] --> (1)

Böylece, istenilen yol 1-->3-->4-->2 ve toplam uzunluk 55 km olarak bulunur.

 

2. FLOYD ALGORÄ°TMASI :

Floyd Algoritması Dijkstra algoritmasının daha genel halidir. Çünkü şebekedeki herhangi iki düğüm arasındaki en kısa yolu belirler. Algoritma, N düğümlü şebekeyi N satırlı ve N sütunlu kare matris olarak gösterir. Matrisin ( i , j ) elemanı, i. düğümden j. düğüme olan uzaklığı verir. i doğrudan j'ye bağlıysa bağlantı değeri, değilse sonsuz değeri alır.

Örnek :

 

Floyd Algoritmasında Uzaklıklar Matrisi ( D ) ve Düğüm Sırası Matrisi ( S ) bulunur. D matrisi bağlantıları birer matematiksel bağıntı olarak ele alır ve ( i, j ) elemanını i. düğümden j. düğüme olan uzaklık olarak seçer. S matrisi düğümlerin bağlanma sırasını tutar. Her i farklı j olmak üzere ( i , j ) = j yapılır. Şebekenin bağlantıları, D ve S matrisleri aşağıda gösterilmiştir.

 

 

Şebeke üzerindeki ilişkilerin bağıntı değerlerini yazalım. Bağlantı olmaması sonsuz uzaklık demektir.

( 1 , 2 ) = 3
( 2 , 1 ) = 3
( 1 , 3 ) = 10
( 3 , 1 ) = 10
( 2 , 4 ) = 5
( 4 , 2 ) = 5

( 3 , 4 ) = 6
( 4 , 3 ) = 6
( 3 , 5 ) = 15
( 4 , 5 ) = 4
( 5 , 4 ) = 4

 

Genel kural; D ( i , j ) karesi için, D ( i, k ) + D ( k , j ) < D ( i , j ) var ise D ( i , j ) = D ( i , k ) + D ( k , j ) yapılır.
S( i , j ) = k yapılır.

 

0. Yineleme : D ve S matrisleri yukarıda şebekenin başlangıç durumunu vermektedir. D matrisindeki sonsuz ifadesi ilgili i ve j düğüm noktalarının bağlı olmadığı anlamına gelir. Ayrıca "-" ile gösterilen veriler de bir düğüm noktasının kendisi ile bağlı olamayacağını belirtir.

 

 

1. Yineleme : Anahtar satır ve sütun, yukarıda da görüldüğü gibi "MAVİ" renkle gösterilmektedir. K = 1'dir. Buna göre mavi kareler haricindeki bütün kareler taranırsa görülecektir ki D ( 2 , 1 ) + D ( 1 , 3 ) < D ( 2 , 3 ) ve D ( 3 , 1 ) + D ( 1 , 2 ) < D ( 3 , 2 ) olduğundan D ( 2 , 3 ) ve D ( 3 , 2 ) karelerinin değerleri (kırmızı kareler) genel kuralda olduğu gibi değiştirilir.
D ( 2 , 3 ) = D ( 2 , 1 ) + D ( 1 , 3 ) ve D ( 3 , 2 ) = D ( 3 , 1 ) + D ( 1 , 2 )
S tablosunda da S ( 2 , 3 ) = 1 ve S ( 3 , 2 ) = 1 yapılır.

 

 

2. Yineleme : K = 2'dir. Genel kural yine tüm beyaz karelere uygulandığunda yukarıdaki gibi D ( 1 , 4 ) ve D ( 4 , 1 ) kareleri değişikliğe uğrar.
D ( 1 , 4 ) = D ( 1 , 2 ) + D ( 2 , 4 ) ve D ( 4 , 1 ) = D ( 4 , 2 ) + D ( 2 , 1 )
S tablosunda da S ( 1 , 4 ) = 2 ve S ( 4 , 1 ) = 2 yapılır.

 

 

3. Yineleme : K = 3'tür. Genel kural yine tüm beyaz karelere uygulandığunda yukarıdaki gibi D ( 1 , 5 ) ve D ( 2 , 5 ) kareleri değişikliğe uğrar.
D ( 1 , 5 ) = D ( 1 , 3 ) + D ( 3 , 5 ) ve D ( 2 , 5 ) = D ( 2 , 3 ) + D ( 3 , 5 )
S tablosunda da S ( 1 , 5 ) = 3 ve S ( 2 , 5 ) = 3 yapılır.

 

 

 

Algoritma bu şekilde N. adıma kadara gider. Tüm adımları yukarıdaki tablolardan görebilirsiniz. Artık şebeke üzerindeki herhangi iki düğüm noktası için gereken tüm bilgiler D ve S tablosunda mevcuttur. Tek yapılması gereken iki tablodan da bilgileri belli bir sistematikle okumaktır.

Örnek 1: 1 ile 5 arasındaki en kısa uzaklık D tablosunda 12 olarak belirtilmiştir. Şimdi rotayı S tablosundan bulalım. S ( i , j ) = j olduğunda tam bağlantı vardır. S ( 1 , 5 ) = 4'tür. O halde 1 ile 5 arasına 4 yazılır. 1 --> 4 --> 5
En baştan itibaren sayılar ikili ikili kontrol edilir. S ( 1 , 4 ) = 2
O halde 1 ile 4 arasına da 2 yazılacaktır. 1 --> 2 --> 4 --> 5
Yine en baştan kontrol edilirse; S( 1 , 2 ) = 2 , S ( 2 , 4 ) = 4 ve S ( 4 , 5 ) = 5 'tir. O halde rota tamamlanmıştır.

 

Örnek 2 : 3.düğüm noktası ile 2. düğüm noktası arasındaki en kısa uzaklığı bulalım. S ( 3 , 2 ) = 4'tür.
O halde 3 ile 2 arasına 4 yazılır. 3 --> 4 --> 2
Bu rotayı ikili ikili kontrol edelim. S( 3 , 4 ) = 4 ve S ( 4 , 2 ) = 2
O halde rota tamamlanmıştır. D ( 3 , 2 ) = 11 olduğundan rota 3 --> 4 --> 2 ve uzaklık 11 birimdir.

Kaynakça : Yöneylem Araştırması ( HAMDY A. TAHA ) , Literatür Yayınları