C# ÖRÜMCEK AĞI EN KISA YOL ALGORİTMASI
Yukarıdaki örümcek ağı verilerek S noktasından F noktasına ulaşılmak isteniyor. Sadece ok ile gösterilen doğrultularda hareket edilebiliyor. En kısa yolu ve toplam alternatif yol adedini bulan algoritmayı tasarlıyacağız.
Öncelikle yollarımızı isimlendirmeyle başlıyoruz.
Daha Sonra int bir diziye yollara göre matris oluşturuyoruz. Bu matris hangi düğümün nereye gidebileceğini gösteriyor.Gidebildiği matrisler 1 gidemediği matrisler 0 olarak değerlerler giriliyor. Ör. 0. düğüm 1,2,3 üncü düğümlere gidebiliyor. 20. düğüme ulaşan düğümler ise 2 değerlerini alıyor.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
int[,] dizi = new int[21, 21] { // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20 /*0 */ { 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, /*1 */ { 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, /*2 */ { 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, /*3 */ { 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, /*4 */ { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, /*5 */ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, /*6 */ { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, /*7 */ { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, /*8 */ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, /*9 */ { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, /*10*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, /*11*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, /*12*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0}, /*13*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}, /*14*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, /*15*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2}, /*16*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0}, /*17*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2}, /*18*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0}, /*19*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2}, /*20*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, }; |
Yukarıdaki Hazırlıklardan sonra Kodlara geçebiliriz.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApp1 { class Program { static void Main(string[] args) { string[] kyol = new string[8];//her adımın yolunu yazdırmak için kullandıgımız dizi. string[] yol=new string[8];//yollarımızın yazıldıgı dizi. int enUzun = 0;//en uzun yol için oluşturduğumuz değişkenimiz int enKisa = 9999;//en kısa yol için oluşturduğumuz değişkenimiz. int olasilikSayac = 0;//olasılık sayısını tutmak için kullandığımız sayaç'ımız. int sayac = 2;//iç içe method kullanırken konum tanımlamarı için kullandığımız değişken. void bul(int[,] mydizi,int satir)//methodumuza oluşturdugumuz dizi ve hangi satırda oldugu parametreleri alıyoruz. { for (int i = 0; i < 21; i++)//hersatır için dönmesi için for döngümüzü 21 kere döndürüyoruz. { if (mydizi[satir, i] == 1)//dizimizden satırda bulunan düğümün i inci elemana gidip gidemediğini kontrol ediyoruz. { sayac++; string yazdir = satir + "-inci satır / " + i + "-inci stun"; Console.Write(yazdir); yol[sayac-2] = yazdir; if(satir == 0) { sayac = 2; } Console.WriteLine(); bul(mydizi, i); sayac--; } else if (mydizi[satir, i] == 2)//eğer değerimiz 2 ise sonuca gelmiş oluyoruz. ve gerekli atamarı yapıyoruz. { satir = 0; olasilikSayac++; Console.Write("-->***geldi sayac ="+(sayac) ); Console.WriteLine(); Console.WriteLine("-------------------------------"); if(sayac>enUzun) { enUzun = sayac; } if (sayac<enKisa) { enKisa = sayac; for (int j = 0; j < 8; j++) { kyol[j] = yol[j]; } } } } } /* */ int[,] dizi = new int[21, 21] { // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20 /*0 */ { 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, /*1 */ { 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, /*2 */ { 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, /*3 */ { 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, /*4 */ { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, /*5 */ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, /*6 */ { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, /*7 */ { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, /*8 */ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, /*9 */ { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, /*10*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, /*11*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, /*12*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0}, /*13*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}, /*14*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, /*15*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2}, /*16*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0}, /*17*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2}, /*18*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0}, /*19*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2}, /*20*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, }; //toplanan dataları ekrana basıyoruz... bul(dizi,0); Console.WriteLine("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@"); Console.WriteLine("Olasılık sayısı :" + olasilikSayac); Console.WriteLine("En kısa yol Basamak sayısı :" + enKisa); Console.WriteLine("En uzun yol Basamak sayısı :" + enUzun); Console.WriteLine("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@"); Console.WriteLine("En Kısa Yol :"); string son=""; for (int i = 0; i < enKisa-1; i++) { Console.WriteLine(kyol[i]); son = kyol[i].Substring(kyol[i].Length-12, 2); } if (son=="15") { Console.WriteLine("15-inci satır / 20-inci stun"); } else if (son == "17") { Console.WriteLine("17-inci satır / 20-inci stun"); } else if (son == "19") { Console.WriteLine("19-inci satır / 20-inci stun"); } Console.WriteLine("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@"); Console.ReadKey(); } } } |