Алгоритм Дейкстры

СОДЕРЖАНИЕ

 

1.ОПИСАНИЕ АЛГОРИТМА………………………………………………………………….3

2.КОД……………………………………………………………………………………………..4

3.РЕЗУЛЬТАТЫ РАБОТЫ……………………………………………………….………….…...7

 

 

 

1. ОПИСАНИЕ  АЛГОРИТМА

 

Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.

Формальное определение

Дан взвешенный неориентированный граф без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины графа до всех остальных вершин этого графа.

 

Логика алгоритма

 

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

 

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

 

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

 

Завершение  выполнения алгоритма. Алгоритм заканчивает работу, когда нельзя больше обработать ни одной вершины.

 

 

 

 

2. КОД

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace alDeikstry

{

    class Graf

    {

        int N; // количество вершин

        bool[,] adj_matrix;// матрица смежности

        int[,] cost; // веса рёбер

        int[]  dist ; // расстояния от заданной вершины

        int[] parent;// из какой вершины пришли

        public Graf()

        {

            N = 100;

            adj_matrix = new bool[N, N];

            cost = new int[N, N];

            dist = new int[N];

            parent = new int[N];

        }

        public void dijkstra(int start)

        {

        // in_tree[i] == true, если для вершины i уже посчитано минимальное расстояние

            bool[] in_tree =new bool[N];

            dist = new int[N];

            parent = new int[N];

            for (int i = 0; i < N; i++)

                parent[i] = 15555;

            for (int i = 0; i < N; i++)

                dist[i] = Int32.MaxValue;

            dist[start] = 0;             

            int cur = start;

            while(!in_tree[cur])

            {

                in_tree[cur] = true;

                for(int i = 0; i < N; i++)

                {

                    if(adj_matrix[cur,i]) 

                    {

                        int d = dist[cur] + cost[cur,i];

                        if(d < dist[i])

                        {

                            dist[i]   = d;  

                            parent[i] = cur;

                        }

                    }     

                }

                int min_dist = Int32.MaxValue;

                for(int i = 0; i < N; i++)

                {

                    if(!in_tree[i] && (dist[i] <  min_dist))

                    {

                        cur      = i;

                        min_dist = dist[i];

                    }

                }

            }

        }

 

 

 

        public void Read()

        {

            Console.WriteLine("Введите количество вершин");

            N = Convert.ToInt32(Console.ReadLine());

            adj_matrix = new bool[N, N];

            bool sm = false;

            Console.WriteLine("Введите 1 если ребро есть, 0 если его нет: ");

            for (int i = 0; i < N; i++)

                for (int j = 0; (i>j)&&(j < N); j++)

                {

                    Console.WriteLine("между вершинами {0} и {1}", i + 1, j + 1);

                    sm = (Convert.ToInt32(Console.ReadLine())==0)?false:true;

                    adj_matrix[i, j] = sm;

                    adj_matrix[j, i] = sm;

                }

            Console.WriteLine("Введите вес ребра: ");

            cost = new int[N, N];

            int ch = Int32.MaxValue;

            for (int i = 0; i < N; i++)

                for (int j = 0; j < N; j++)

                    cost[i, j] = ch;

            for (int i = 0; i < N; i++)

                for (int j = 0; (i>j)&&(j < N); j++)

                    if (adj_matrix[i, j] == true)

                    {

                        Console.WriteLine("между вершинами {0} и {1}", i + 1, j + 1);

                        ch = Convert.ToInt32(Console.ReadLine());

                        cost[i, j] = ch;

                        cost[j, i] = ch;

                    }

        }

        public void Write()

        {

            Console.WriteLine("матрица имеет вид:"); 

            for (int i = 0; i < N; i++)

            {

                Console.Write("\n");

                for (int j = 0; j < N; j++)

                    Console.Write("{0,5}  ", (adj_matrix [i, j] == true?1:0));

                Console.WriteLine();

            }

            Console.WriteLine("вес :");

            for (int i = 0; i < N; i++)

            {

                Console.Write("\n");

                for (int j = 0; j < N; j++)

                    Console.Write("{0,5}  ", (cost[i,j]==int.MaxValue)?0:cost [i, j]);

                Console.WriteLine();

             }

        }

        public void WritePut(int Start)

        {

            Console.WriteLine("кратчайший путь от {0}  :", Start +1);

                for (int i = 0; i < dist.Length; i++)

                    Console.WriteLine("до {0} равен {1}", i+1, dist[i]);

        }

    }

 

 

 

 

 

 

 

 

    class Program

    {

        static void Main(string[] args)

        {

            Graf m_Graf = new Graf();

            m_Graf.Read();

            m_Graf.Write();

            Console.WriteLine("введите стартовую вершину");

            int Start = Convert.ToInt32(Console.ReadLine()) - 1;

            m_Graf.dijkstra(Start);

            m_Graf.WritePut(Start);

            Console.ReadKey();

        }

    }

}

 

   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. РЕЗУЛЬТАТЫ  РАБОТЫ