Алгоритъм на Дейкстра

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене
Начин на обхождане на алгоритъма на Дейкстра

Алгоритъмът на Дейкстра, наречен на автора си Едсхер Дейкстра (Edsger Dijkstra), служи за пресмятане на най-къс път от даден връх до всички останали върхове на граф с неотрицателни тегла на ребрата. Графът може да бъде ориентиран или неориентиран. Резултатът от работата на алгоритъма е дърво на най-късите пътища с начало дадения връх. Алгоритъмът се използва още за намиране на най-къс път от един даден връх до друг даден връх; в този случай алгоритъмът спира работа, след като е намерил най-краткия път между тези два върха.

Пример: Всяка пътна карта може да се разглежда като граф. Върховете на графа са градовете, а ребрата са шосетата между градовете.

Алгоритъмът на Дейкстра се основава на една идея, наречена релаксация: във всеки момент от работата на алгоритъма за всеки връх се пази информация за най-късия път, намерен до момента; ако след това алгоритъмът намери по-добър път, тази информация се актуализира. Същата идея се използва и в други алгоритми, аналогични на алгоритъма на Дейкстра: за търсене на най-широк път, за построяване на минимално покриващо дърво и др. Ето защо алгоритъмът на Дейкстра и неговите аналози се използват широко в практиката, например в мрежовите протоколи за маршрутизация, най-вече в IS-IS и OSPF, както и в програмите за GPS устройства с цел оптимизация на транспорта.

Алгоритъмът на Дейкстра работи само ако теглата на ребрата са неотрицателни. За графи, в които има ребра с отрицателни тегла, са разработени други алгоритми: алгоритъмът на БелманФорд и алгоритъмът на Флойд—Уоршал.

История[редактиране | редактиране на кода]

Докато работи в Математическия център в Амстердам през 1956 г. като програмист, Едсхер Дейкстра търсел начин да демонстрира възможностите на нов компютър, наречен ARMAC. За целта трябвало да избере задача, която може да бъде решена от компютър, но същевременно е разбираема за хората, които не работят с компютри. Дейкстра се спрял на задачата за намирането на най-къс път, и след като създал алгоритъма, го програмирал за машината ARMAC, като използвал опростена транспортна карта на 64 града в Холандия (ARMAC бил 6-битов компютър и затова можел да пази информация само за 64 града). Година по-късно Дейкстра се натъкнал на друг проблем, поставен от инженери, работещи по следващия модел компютър на института: минимизиране на количеството тел, необходимо за свързване на изводите на задния панел на устройството. Дейкстра предложил решение, като на практика преоткрил алгоритъма на Прим—Ярник за построяване на минимално покриващо дърво. Дейкстра публикувал този алгоритъм през 1959 г. — две години след Прим и двадесет и девет години след Ярник.

Описание на алгоритъма[редактиране | редактиране на кода]

Алгоритъмът на Дейкстра използва релаксация. За всеки връх се пази по едно число, показващо дължината най-късия път, намерен до момента, до този връх. Отначало (когато все още не е открит никакъв път) тези числа са равни на безкрайност, а в течение на работата на алгоритъма намаляват при откриване на все по-къси пътища.

Нека r е избраният начален връх, а w(i, j ) е теглото на реброто от върха i до върха j (w(i, j ) е равно на безкрайност, ако между двата върха няма ребро). Алгоритъмът работи, като за всеки връх i пази дължината d(i) на намерения до момента най-къс път от r до i и кандидата π(i) за ребро, чрез което върхът i да бъде включен в строящото се дърво на най-къси пътища (π(i) е едно от ребрата, влизащи в i ). Алгоритъмът постепенно разширява множеството S от върховете, за които намерената дължина със сигурност е минимална, т.е. добавя нови върхове към дървото. Първоначално S = { r }, d(r) = 0, π(r) = NULL , d(i)=безкрайност и π(i) = NULL за всеки връх i, различен от r. На всяка итерация от върховете, които не са в S, алгоритъмът избира онзи връх v, за който числото d(v) е минимално. Върхът v се добавя в S, т.е. реброто π(v) се добавя към дървото, след което се извършва релаксация: за всеки връх j, който не е в S, d(j) = min(d(j), d(v) + w(v, j )) и ако второто число е по-малко, то π(j) = (v, j ). Алгоритъмът приключва, когато всички върхове на графа са в множеството S.

Доказателство за коректност[редактиране | редактиране на кода]

Доказателство за коректност на алгоритъма на Дейкстра чрез индукция по броя на посетените върхове (върховете от множеството S):

Инварианта: Ако върхът v е посетен, то d(v) = дължината на най-къс път от r до v , а π(v) е последното ребро от този път; в противен случай d(v) = дължината на най-къс път от r до v , минаващ само през посетени върхове с изключение на върха v, а π(v) е последното ребро от този път. (Ако множеството от възможните пътища е празно, то минималната дължина се счита за безкрайност, а последното ребро е неопределено.)

База: Когато има само един посетен възел, а именно r, твърдението е вярно: най-късият път от r до r съдържа един връх (r) и нула ребра, дължината му е нула, колкото е стойността на d(r), а последно ребро няма (π(r) = NULL); до останалите върхове все още не са открити пътища, затова d(v) = безкрайност и π(v) = NULL.

Индуктивна стъпка: Нека инвариантата е в сила, когато посетените върхове са k–1 на брой. Ще докажем, че тя остава в сила, когато посетените върхове станат k броя.

Че включването в S на върха v с минимално d(v) е правилно, т.е. че d(v) е дължината не само на най-късия път от r до v, минаващ само през вече посетени върхове, а на най-късия път от r до v изобщо, се доказва така: Ако допуснем противното, т.е. че има по-къс път от r до v, то той трябва да минава през непосетен връх (различен от v). Ако u е първият такъв връх в пътя, то по дължината на пътя върхът u идва преди върха v, затова d(u) = дължината на най-късия път от r до u (вече намерен според индуктивното предположение) е по-малка или равна на разстоянието от r до v по този най-къс път, което е по-малко от d(v) според направеното допускане. Излиза, че d(u) < d(v), което противоречи на избора на v.

Че до всички върхове от новото множество непосетени върхове (върхът v вече е маркиран като посетен) са намерени най-късите пътища, минаващи само през посетени върхове, следва така: Тези най-къси пътища или не минават през новия посетен връх (v), или минават през него. В първия случай те са били намерени още на предишната стъпка съгласно с индукционното предположение. Във втория случай те ще бъдат намерени по време на релаксацията.

С това е доказана правилността на инвариантата

Завършек: Алгоритъмът непременно ще завърши работа, тъй като на всяка стъпка се добавя по един връх към S, а множеството от върховете е крайно. След последната итерация S съдържа всички върхове на графа и от доказаната инварианта следва, че алгоритъмът е намерил най-късите пътища до всички върхове.

Сложност[редактиране | редактиране на кода]

Нека алгоритъмът се прилага върху граф G(V, E). Най-простата реализация използва матрица на съседство за представяне на графа и едномерен вектор за съхранение на стойностите на d(). Сложността по време и по памет е O(|V|2). Ако графът бъде представен чрез списъци на съседите и за намиране на всеки следващ връх се използва приоритетна опашка, то при подходяща реализация сложността по време е O(E + |V|.log|V|), а по памет е O(|E|+|V|).

Използване на алгоритъма на Дейкстра в програмния език C#[редактиране | редактиране на кода]

   class Dijkstra
   {
       private int[,] mapMatrix;
       private int[] distance;
       private int[] visitedNodes;
       private void DijikstraAlgorithm()
       {
           for (int i = 0; i < this.distance.Length; i++)
           {
               if (this.mapMatrix[0, i] == 0)
               {
                   this.distance[i] = int.MaxValue;
               }
               else
               {
                   this.distance[i] = this.mapMatrix[0, i];
               }
               this.visitedNodes[i] = i;
           }
           this.visitedNodes[0] = -1;
           for (int j = 0; j < this.distance.Length / 2; j++)
           {
               int currentShortestWay = int.MaxValue;
               int nextNodeOnShortestWay = 0;
               for (int i = 0; i < this.distance.Length; i++)
               {
                   if ((this.distance[i] < currentShortestWay) && (this.visitedNodes[i] != -1))
                   {
                       currentShortestWay = this.distance[i];
                       nextNodeOnShortestWay = i;
                   }
               }
               for (int i = 0; i < this.distance.Length; i++)
               {
                   if (this.visitedNodes[i] != -1)
                   {
                       if (this.mapMatrix[nextNodeOnShortestWay, i] != 0)
                       {
                           if (this.distance[i] > this.distance[nextNodeOnShortestWay] + 
                                   this.mapMatrix[nextNodeOnShortestWay, i])
                           {
                               int newDistance = this.distance[nextNodeOnShortestWay] + 
                                   this.mapMatrix[nextNodeOnShortestWay, i];
                               this.distance[i] = newDistance; 
                           }
                       }
                   }
               }
               this.visitedNodes[nextNodeOnShortestWay] = -1;
           }
       }
       private void CreateMap()
       {
           this.mapMatrix = new int[,]
           {
               {0, 7, 9, 0, 0, 14},
               {7, 0, 10, 15, 0, 0},
               {9, 10, 0, 11, 0, 2},
               {0, 15, 11, 0, 6, 0},
               {0, 0, 0, 6, 0, 9}, 
               {14, 0, 2, 0, 9, 0}
           };
           this.distance = new int[this.mapMatrix.GetLength(0)];
           this.visitedNodes = new int[this.mapMatrix.GetLength(0)];
       }
       private void PrintShortestWays()
       {
           for (int i = 0; i < this.distance.Length; i++)
           {
               if (this.distance[i] == int.MaxValue)
               {
                   Console.WriteLine("The shortest way to node: {0}, is - \"start point\"", i + 1);
               }
               else
               {
                   Console.WriteLine("The shortest way to node: {0}, is - {1}",
                       i + 1, this.distance[i]);
               }
           }
       }
       static void Main(string[] args)
       {
           Dijkstra test = new Dijkstra();
           test.CreateMap();
           test.DijikstraAlgorithm();
           test.PrintShortestWays();
       }
   }

Сродни проблеми и алгоритми[редактиране | редактиране на кода]

Ужасен  машинен  превод!  Има  спешна  нужда от редактиране!

Функционалността на оригиналния алгоритъм на Дейкстра може да бъде разширена с най-различни модификации. Например понякога е желателно да се представи решение, което съдържа не само оптималните пътища, но и някои субоптимални (т.е. с дължина, малко по-голяма от минималната). За целта първо се намират най-късите пътища. Един ръб се появява в оптималното решение и се отстранява от графиката, и оптимално решение на този нов графика се изчислява. Всеки ръб на първоначалния разтвор се подтиска от своя страна и нов най-кратък път се изчислява. След това вторични решения са подредени и представени след първото оптималното решение.

Алгоритъм на Дейкстра обикновено е работния принцип зад линк състояние протоколи за маршрутизация, OSPF и Е-е най-често срещаните.

За разлика Алгоритъм на Дейкстра, алгоритъм на Белман-Ford може да се използва върху графики с отрицателен край тежести, толкова дълго, колкото графиката не съдържа отрицателен цикъл постижим от източник връх те години. Наличието на тези цикли означава, че няма кратък път, тъй като общото тегло става по време на всеки цикъл се премества. Възможно е да се адаптира алгоритъм на Дейсктра да се справи с отрицателни тегло на ръбове чрез комбиниране с алгоритъм Белман-Ford (за отстраняване на отрицателните ръбове и откриване отрицателни цикъла), като алгоритъм се нарича алгоритъм Джонсън.

The A * алгоритъм е обобщение на Алгоритъма на Дейкстра, че разфасовки определяне на размера на подграф, че трябва да се проучи, ако наличие на допълнителна информация, която осигурява по-ниска граница на "разстоянието" до целта. Този подход може да се разглежда от гледна точка на линейното програмиране: има естествена линейна програма за изчисляване на най-кратките пътища и решения на своята двойна линейна програма са осъществими, ако и само ако те са в последователен евристичен (казано грубо, тъй като конвенциите на знакови различават от място на място в литературата). Това е възможно с двойна / последователна евристично определяне на неотрицателно намалени разходи и A * е по същество работи Алгоритъм на Дейкстра с тези намалени разходи. Ако двойните отговарят на по-слабата положение, свързано допустимост, тогава A * е вместо по-близко до алгоритъма на Белман-Форд.

Процесът, който лежи в основата на Алгоритъм на Дейкстра е подобен на "алчния процес" използва в алгоритъм на Прим. Целта на Прим е да намери минимум обхваща дърво, което свързва всички възли в графиката; Дейкстра се занимава само с две възли. Прим не цени общото тегло на пътя от изходния възел, само отделния път.

"Първо търсене на ширината" е търсене, което може да се разглежда като специален случай на Алгоритъм на Дейкстра за непретеглени графики, където е приоритетната опашка превръща в опашка FIFO.

"Бързия метод на маршируване(Линеен метод)" може да се разглежда като непрекъсната версия на Алгоритъм на Дейкстра, който изчислява геодезични разстоянието на триъгълното окото.

Външни препратки[редактиране | редактиране на кода]

Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „Dijkstra's algorithm“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница. Вижте източниците на оригиналната статия, състоянието ѝ при превода, и списъка на съавторите.