Aktif KonularAktif Konular  Forum Üyelerini GösterÜye Listesi  TakvimTakvim  Forumu AraArama  YardımYardım
  Kayıt OlKayıt Ol  GirişGiriş
C / C++ ve C++.NET
 C#nedir?com Forum : C/C++ : C / C++ ve C++.NET
Mesaj icon Konu: Dijkstra Algoritması - Dijkstra’s Algorithm Yanıt Yaz Yeni Konu Gönder
   

Yazar Mesaj
CrazySayisalci
Senior Member
Senior Member


Kayıt Tarihi: 14 Mayıs 2009
Aktif Durum: Aktif Değil
Gönderilenler: 686
Alıntı CrazySayisalci Cevaplabullet Konu: Dijkstra Algoritması - Dijkstra’s Algorithm
    Gönderim Zamanı: 19 Mayıs 2009 Saat 22:30
Dijkstra Algoritması - Dijkstra’s Algorithm

Dijkstra Algortiması, bir graf üzerinde istenilen bir düğümden, graftaki diğer tüm düğümlere giden minimum maliyetli yolları (shortest path) bulmak için kullanılan bir algoritmadır. Algoritmayı şu şekilde açıklayabiliriz:

Başlangıçta kullanıcının verdiği kaynak düğüm sadece kendisinden haberdardır. İlk iş olarak, bu kaynak düğümden doğrudan ulaşılabilen en az maliyetli düğüm araştırılıyor. Bu düğüm, haberdar olunan (kaynaktan minimum uzaklığı bilinen) düğümler kümesine ekleniyor.

Haberdar olunan düğümlerden doğrudan ulaşılabilen düğümler içinde en az maliyetli (kaynağa uzaklık bakımından en yakın) olan yeni bir düğüm araştırılıyor. Bu düğüm de haberdar olunan düğümler kümesine ekleniyor. Böylece en sonda, ulaşılması mümkün olan tüm düğünlerden haberdar olunması amaçlanıyor. Yeni düğümler bulunduğu sürece bu işleme devam ediliyor.

Aşağıda, yönlü bir graf için, Dijkstra Algoritmanın C++ dilinde yazılmış kaynak kodu bulunmaktadır.
 


//———————————————————————–

//———————————————————————–

#include <iostream>
#include <vector>
using namespace std;

//———————————————————————–

struct hedef
{
int dugum;
int maliyet;
};

//———————————————————————–
//
// Grafta bulunan ayrıt, her iki ucundan bir düğüme bağlıdır.
// Bu düğümlerin numaraları “dugum1″ ve “dugum2″ dir.
// Ayrıtın yönü ise, birinci düğümden ikinci düğüme doğrudur.
//
//———————————————————————–

struct ayrit
{
int maliyet;
int dugum1;
int dugum2;

// ayrit sınıfı için yapıcı.
ayrit (int d1, int d2, int m)
{
dugum1 = d1;
dugum2 = d2;
maliyet = m;
}
};

//—————————– dijkstra ———————————
//
// Amaç : Verilen bir graf üzerinde, istenilen bir düğümü, graftaki diğer
// tüm düğümlere ulaştıran minimum maliyetli yolları bulmak
//
// Giriş parametresi : Kaynak düğüm, Üzerinde çalışılan graf,
//
// Dönüş değeri : Minimum uzunluklu yolların değerlerini tutan vektör.
//
// Fonksiyonda, minimum maliyetteki yolları bulma işlemi, dijkstra
// algoritması ile gerçeklenmiştir.
//
//———————————————————————–

vector<hedef> dijkstra (int kaynak, vector<ayrit>& G)
{
vector<int> D; // Kullanıcının girdiği kaynak düğüme olan uzaklığı
// bilinen düğümleri (haberdar olunan düğümleri) tutmak için
vector<hedef> S(1); // Sonucu tutmak için
hedef h;

// Kullanıcının verdiği kaynak düğüm kendisinden haberdar.
D.push_back (kaynak);

// Verilen kaynak düğümün kendisine olan uzaklığı sıfır.
// Bu bilgi, sonuç vektörüne yazılıyor.
S[0].dugum = kaynak;
S[0].maliyet = 0;

// Ulaşabileceğimiz tüm düğümler incelendi mı?
// Araştırılacak düğüm kalmayana kadar devam et.
while (1)
{
int minMaliyet = RAND_MAX; // Haberdar olunan düğümler kümesinden doğrudan
// ulaşılabilen ve kaynağa göre minimum maliyetli
// düğümün maliyet değeri
int yeniDugum; // Haberdar olunacak yeni düğümün numarası

// En yakın yeni komşuyu bulabilmek için,
// haberdar olunan düğümler kümesinin her elemanının sahip olduğu
// komşularının, kaynak düğümden olan uzaklıklarına bakılıyor.
// Bunların en minimum olanı seçilecek.

// haberdar olunan düğümlere tek tek bak
for (int i = 0; i < D.size (); i ++)
{
// D düğümünden daha önce haberdar olunduğu için, bu düğümün
// kaynağa göre maliyeti sonuç matrisi içinde yazılıdır.
// for sonucunda oluşan a, bu yeri tutan değişken olacak.
for (int a = 0; a < S.size (); a ++)
if (S[a].dugum == D)
break;

// Graf üzerindeki tüm ayrıtlara bakılıyor
for (int j = 0; j < G.size (); j ++)
{
// Bakılan ayrıtın ilk ucu komşularını araştırdığımız düğüm mü?
// Amacımız D ayrıtının komşularından en az maliyetli olanı
// bulmak olduğu için, şu an sadece bu ayrıtlar bizi ilgilendiriyor.
// Ayrıtın yönü birinci düğümden ikinci düğüme doğru olduğu için,
// ayrıtın ilk ucuna bakılıyor. Diğer uç ise komşu düğümdür.
if (G[j].dugum1 == D)
{
h.dugum = G[j].dugum2; // Bu if içerisinde h değişkeni
// komşu düğümü ifade etmek için
// kullanılıyor. Ayrıtın diğer
// ucu ise komşu düğümdür.

// Komşu düğümden daha önceden haberdar olunup
// olunmadığına bakılıyor. Eğer zaten, bu düğüm için
// minimum maliyetli yol biliniyorsa, bu düğüm es geçiliyor.
// Daha önceden bu düğümden haberdar olunup olunmadığını
// anlamanın yolu, sonuç vektörü üzerinde bu düğüme ait bir
// bilginin yazılı olup olmadığına bakmaktır.
for (int k = 0; k < S.size (); k ++)
if (S[k].dugum == h.dugum)
break;

// Daha önceden bu düğümün maliyeti bilinmiyor ise
if (k == S.size ())
{
// Bu düğüm için maliyet değeri hesaplanıyor.
// Kullanıcının verdiği kaynak düğümün, D
// düğümüne olan mesafesi (maliyeti) biliniyor.
// Bu değer S[a].maliyet değişkenindde saklıdır.
h.maliyet = S[a].maliyet + G[j].maliyet;

// Bu maliyetin, şimdiye kadar incelenen
// komşular içindeki en küçük maliyetten
// daha küçük olup olmadığına bakılıyor.
// Böylece en sonda, haberdar olunan
// düğümlere eklemek için en az maliyetli
// düğüme ulaşılmış olunacak.
if (minMaliyet > h.maliyet)
{
// En küçük maliyet artık bu maliyet
minMaliyet = h.maliyet;

// Daha az maliyetli başka bir düğüm çıkmazsa,
// eklenecek yeni düğüm bu düğümdür.
yeniDugum = h.dugum;
}
}
}
}
}

// minMaliyet değerinin RAND_MAX olarak kalmış olması,
// yeni bir düğüme ulaşılamamış olduğunu gösteriyor.
// Haberdar olunan düğümlere eklemek için yeni bir düğüm
// bulunamadı. Ulaşılınabilecek tüm düğümlere ulaşıldı
if (minMaliyet == RAND_MAX) return S;

// h eklenecek yeni düğümü gösteriyor.
h.dugum = yeniDugum;
h.maliyet = minMaliyet;

// Bu düğümü bilinen düğümler listesine ekle.
D.push_back (h.dugum);

// Yeni düğümle ilgili bilgiyi sonuç vektörüne yaz.
S.push_back (h);
}

return S;
}

//—————————— main ———————————–

int main ()
{
vector<hedef> S;
vector<ayrit> G;

// Graf oluşturuluyor.
G.push_back (ayrit (5, 6, 15));
G.push_back (ayrit (5, 4, 20));
G.push_back (ayrit (6, 4, 12));
G.push_back (ayrit (6, 1, 28));
G.push_back (ayrit (1, 2, 24));
G.push_back (ayrit (4, 3, 13));
G.push_back (ayrit (2, 3, 11));

S = dijkstra (6, G);

return 0;
}

//—————————— end ———————————-

Yukarıdaki algoritma, yönlü graflar için yazılmıştır. Eğer aynı algoritmayı yönsüz graflar için yazmak istersek aşağıdaki değişikliği yapmamız gerekecektir.
if (G[j].dugum1 == D)
{
h.dugum = G[j].dugum2;

…

satırları yerine
int k = 0;

if (G[j].dugum1 == D)
{
h.dugum = G[j].dugum2;

k = 1;
}

else if (G[j].dugum2 == D)
{
h.dugum = G[j].dugum1;

k = 1;
}

if (k)
{
…

satırlarını yazmamız yeterli olacaktır. Grafı tanımlarken verilen birinci düğümler kaynak, iki düğümler ise hedef olarak belirlenmiştir. Ayrıtın yönü de kaynaktan hedefe doğru olduğu için, yönlü grafta bir düğümün komşuları araştırılırken, bizim için geçerli olan graf üzerinde sadece birinci noktası kaynak olan düğümleri bulup, bunların diğer uçlarına bakmaktı. Fakat graf yönsüz graf olunca, amacımız D‘nin bulunduğu ayrıtları bulmak olacağından, ayrıtın uçlarından herhangi birinin haberdar olduğumuz nokta (D) olması bizim için yeterlidir.

Algoritmaya parametre olarak, kendisine ulaşılması mümkün olmayan düğümleri içeren bir graf verildiği zaman, bu düğümler hakkında bir bilgi geri döndürülmez. Ya fonksiyondan geri dönen vektöre bakıp, hakkında maliyet bilgisi bulamadığımız bir düğüm gördüğümüzde bu düğüme ulaşmamın mümkün olmadığını anlayabiliriz, ya da fonksiyonun sonunda böyle düğümleri tespit edip sonuç vektörüne uygun bir şekilde ekleyebiliriz.

Dikkat edilirse, fonksiyondan geriye sadece, herbir düğüme ulaştıran en kısa yolun maliyet bilgisi döndürüldü. Eğer bu yol üzerinde hangi noktaların bulunduğu bilgisini de elde etmek istiyorsak kod üzerinde aşağıdaki değişiklikleri yapmamız gerekecektir.
struct hedef
{
int dugum;
int maliyet;
};

hedef sınıfı içerisine
struct hedef
{
int dugum;
int maliyet;
vector<int> yol; // Yol üzerindeki düğümleri tutmak için kuyruk.
};

yol üzerindeki düğümleri tutmak için bir vektör eklenmelidir. Ayrıca
S[0].maliyet = 0;
satırından sonra
S[0].yol.push_back (kaynak);

while (1)
satırından sonra
int p;

yeniDugum = h.dugum;
satırından sonra
p = a;

S.push_back (h);
satırı yerine de
h.yol = S

.yol;
h.yol.push_back (h.dugum);
S.push_back (h);
h.yol.clear ();

satırlarını eklememmiz gerekecektir. Bu satırlar ile, yeni bir düğüme ulaşıldığında, bizi o düğüme götüren yol bilgisi sonuç vektöründe tutulmuş olacaktır.

Eğer oluşan sonuç vektörünü ekrana bastırmak istersek main fonksiyon içerisinde aşağıdaki satırlara yer vermemiz gerekecektir.
cout << “Hedef\tMaliyet\tYol\n”;

for (int i = 0; i < S.size (); i ++)
{
cout << S.dugum << “\t” << S.maliyet << “\t”;

// Yol üzerindeki düğümleri ekrana yaz.
for (int j= 0; j < S.yol.size (); j ++)
cout << S.yol[j] << ” “;

cout << endl;
}

Floyd-Warshall Algoritması / Floyd-Warshall Algorithm
Warshall Algortiması, bir graf üzerinde tüm düğüm çiftleri arasındaki minimum uzaklığı (shortest path) bulmak için kullanılan bir algoritmadır. Bunun için her (i , k) düğüm çifti için aşağıdaki eşitliğe bakılır:

D [i , j] = min (D [i , j] , D [i , k] + D [k , j])

Yani, i düğümünden j düğümüne gitmek için bir yeni bir k düğümü üzerinden geçilen başka bir yol bulunmuşsa ve bulunan bu yeni yolun daha az maliyetli olduğu anlaşılırsa i ve j arasındaki yeni yol, bu yol olarak seçilir.

Aşağıda, yönlü bir graf için, Floyd Algoritmanın C dilinde yazılmış kaynak kodu gözükmektedir.

//———————————————————————–

//———————————————————————–

#include <stdio.h>
#include <stdlib.h>

#define N 4 // Düğüm Sayısı
#define R RAND_MAX // Sonsuz Uzaklık

//—————————— main ———————————–

int main()
{
// G[j], i ve j düğümleri arasındaki mesafeyi gösteriyor.
// Bir düğümün kendisine olan uzaklığı sıfır, doğrudan ulaşamadığı
// düğüme olan uzaklığı ise sonsuz (RAND_MAX) alınmıştır.
int G[N][N] = { 0, 5, R, R,
50, 0, 15, 5,
30, R, 0, 15,
15, R, 5, 0};

int i, j, k;

// Her k ara düğümü için, graf üzerindeki tüm düğüm çiftlerine
// bakılarak, i ve j düğümleri arasında, bu k düğümünden geçen
// ve daha kısa olan yeni bir yol araştırılıyor.
for (k = 0; k < N; k++)
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (G[j] > (G[k] + G[k][j]))
G[j] = G[k] + G[k][j];

return 0;
}

Eğer aynı algoritmayı yönsüz graf için yazmak istersek, matris simetrik olacağı için matrisin sadece tek tarafına bakmak yeterli olacaktır. Bunun için j < N yerine j <= i yazmamız yeterli olacaktır.

Omeranar1@Hotmail.CoM
Niğde Üniv. Elektrik Elektronik Müh. (2.Sınıf)
Bildiğimi Bu Sitede Öğrendim
IP
   

Yanıt Yaz Yeni Konu Gönder
Konuyu Yazdır Konuyu Yazdır

Forum Atla
Kapalı Foruma Yeni Konu Gönderme
Kapalı Forumdaki Konulara Cevap Yazma
Kapalı Forumda Cevapları Silme
Kapalı Forumdaki Cevapları Düzenleme
Kapalı Forumda Anket Açma
Kapalı Forumda Anketlerde Oy Kullanma

Bulletin Board Software by Web Wiz Forums version 8.03
Copyright ©2001-2006 Web Wiz Guide