gokhanca.com

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ı