Алгоритъм на Дейкстра
Алгоритъмът на Дейкстра, наречен на автора си Едсхер Дейкстра (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();
}
}
Външни препратки
[редактиране | редактиране на кода]- Анимация, показваща действието на алгоритъма
- The Boost Graph Library (BGL)
- Javascript имплементация на алгоритъма Архив на оригинала от 2006-07-02 в Wayback Machine.
- Interactive Implementation of Dijkstra's Algorithm Архив на оригинала от 2020-02-17 в Wayback Machine.
- Проблемът за най-късо трасе: Алгоритъм на Дейкстра Архив на оригинала от 2007-09-27 в Wayback Machine.
- Dijkstra's Algorithm Applet
- Направи си сам! Дефинирай свой граф и изпълни алгоритъма! Аплет на Карла Лафра от университета „Пейс“
 
|
Тази страница частично или изцяло представлява превод на страницата Dijkstra's algorithm в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.
ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни. |