Developersland

Teknoloji ve Yazılım Blogu

  • Yazıtipi boyutunu arttır
  • Varsayılan yazıtipi boyutu
  • Yazıtipi boyutunu azaltır

Bellman Ford Algorithm Implementation (C#.Net)

DOWNLOAD SOURCE CODE (58 KB)

Bellman Ford Algoritması node'lar arasındaki en kısa yolu bulmak için kullanılan bir algoritmadır.
Öncelikle gri renkteki kutuda node'larımız arasındaki edgeleri tanımlıyoruz. Daha sonra başlangıç node'unu belirliyoruz (A için 1 örneğin)
Oluşacak yol sol kısımda çizilecektir. Ayrıca bilgiler de açık yeşil renkteki kutucuktan kontrol edilebilecektir.
Program ayrıca çalıştırıldıktan sonra negative cycle kontrolü yaparak bir messageBox vasıtasıyla kullanıcıya bu konuda bildirim yapmaktadır.


bellman ford algorithm


using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

 

namespace BFS

{

    public partial class Form1 : Form

    {

        public Form1()

        {

            InitializeComponent();

        }

 

        private void Form1_Load(object sender, EventArgs e)

        {

            numericUpDown1.Value = 5;

            richTextBox1.Text = "0,5,8,-4,0\n" +

                                "-2,0,0,0,0\n" +

                                "0,-3,0,9,0\n" +

                                "0,7,0,0,2\n" +

                                "6,0,7,0,0";

                              

                               

        }

        List<Edge> edges = new List<Edge>();

        List<Node> nodes = new List<Node>();

        private void button1_Click(object sender, EventArgs e)

        {

            richTextBox2.Text = "";

            nodes.Clear();

            String s = richTextBox1.Text;

            String[] rows = s.Split('\n');

 

            int index = 0;

            foreach (string str in rows)

            {

                Node nn = new Node();

                nodes.Add(nn);

            }

 

            foreach (string str in rows)

            {

                String[] temp = str.Split(',');

                int i = 0;

                foreach (string a in temp)

                {

                    if (Convert.ToInt32(a) != 0)

                    {

                        nodes[index].komsular.Add(nodes[i]);

                        Edge edge = new Edge(nodes[index], nodes[i], Convert.ToInt32(a));

                        edges.Add(edge);

                    }

                    i++;

                }

                nodes[index].number = index;

                index++;

            }

            //Buraya kadar inputları aldık ve listelere aktardık.

            bellmanFord();

            print();

        }

        void bellmanFord()

        {

            initialize();

            for (int i = 0; i <= nodes.Count - 2; i++)

            {

                foreach (Edge edge in edges)

                {

                    relax(edge.n1, edge.n2);

                }

            }

            if (detectingNegativeCycles())

            {

                MessageBox.Show("Negative Cycle Algılanmadı!");

            }

            else

            {

                MessageBox.Show("Negative Cycle Algılandı!");

            }

            ciz();

           

        }

 

        bool detectingNegativeCycles()

        {

            foreach (Edge edge in edges)

            {

                if (edge.n2.deger > edge.n1.deger + getWeight(edge.n1, edge.n2))

                {

                    return false;

                }

            }

            return true;

        }

 

 

        void initialize()

        {

            foreach (Node n in nodes)

            {

                n.deger = 10000;

                n.parent = null;

            }

            nodes[Convert.ToInt32(numericUpDown1.Value-1)].deger = 0;

        }

 

        void relax(Node n1,Node n2)

        {

            if (n2.deger > (n1.deger + getWeight(n1, n2)))

            {

                n2.deger = n1.deger + getWeight(n1, n2);

                n2.parent = n1;

            }

        }

 

        int getWeight(Node n1,Node n2)

        {

            int sonuc = -1;

            foreach (Edge edg in edges)

            {

                if (edg.n1 == n1 && edg.n2 == n2)

                {

                    sonuc = edg.weight;

                }

            }

            return sonuc;

        }

 

        int yatay = 100;

        int dikey = 100;

        System.Drawing.Graphics graphicsObj;

        Font myFont = new System.Drawing.Font("Helvetica", 25, FontStyle.Regular);

        Brush myBrush = new SolidBrush(System.Drawing.Color.Yellow);

        Brush myBrush2 = new SolidBrush(System.Drawing.Color.Gray);

        Brush myBrush3 = new SolidBrush(System.Drawing.Color.Black);

        Pen myPen = new Pen(System.Drawing.Color.White, 5);

        Pen myPen1 = new Pen(System.Drawing.Color.Yellow, 5);

        Pen myPen2 = new Pen(System.Drawing.Color.Green, 5);

           

 

 

        public void ciz()

        {

            graphicsObj = this.CreateGraphics();

            for (int i = 1; i <= nodes.Count; i++)

            {

                Rectangle myRectangle = new Rectangle(yatay, dikey, 40, 40);

                graphicsObj.DrawEllipse(myPen, myRectangle);

                graphicsObj.DrawString(nodes[i - 1].ad(), myFont, myBrush, yatay, dikey);

                nodes[i - 1].p = new Point(yatay + 20, dikey + 20);

                yatay += 100;

 

                if ((i % 3) == 0)

                {

                    dikey += 150;

                    yatay = 100;

                }

 

                if ((i % 2) == 0)

                {

                    dikey -= 20;

                }

            }

 

 

            foreach (Node n in nodes)

            {

                if(n.parent!=null)

                graphicsObj.DrawLine(myPen2, n.p, n.parent.p);

            }

        }

 

        void print()

        {

            foreach (Node n in nodes)

            {

                richTextBox2.Text += "\n" + n.ad() + "\nDeger: " + n.deger.ToString() ;

 

                if (n.parent != null)

                {

                    richTextBox2.Text += "\nParent: " + n.parent.ad();

                }

                else

                {

                    richTextBox2.Text += "\nParent: KENDİSİ ROOT";

                }

                foreach (Node k in n.komsular)

                {

                    richTextBox2.Text += "\n"+k.ad()+" komşusu ile arasındaki weight: "+getWeight(n, k);

                }

            }

        }

    }

}

 



 

Yorum ekle


Güvenlik kodu
Yenile