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

Описание

Входът на алгоритъма е претеглен насочен график с дъги с неотрицателно тегло. Резултатът е набор от най-кратки пътища от даден връх до други.

В началото разстоянието за началния връх се приема за нула, а разстоянията до всички останали се считат за безкрайни. Масив от флагове, показващи дали върхът е преминат, се запълва с нули. След това на всяка стъпка от цикъла се търси връх с минимално разстояние до началния и флаг равен на нула. За него се задава флаг и се проверяват всички съседни върхове. Ако предварително изчисленото разстояние от изходния връх до проверения връх е по-голямо от сумата от разстоянието до текущия връх и дължината на ръба от него до проверения връх, тогава разстоянието до проверения връх се приравнява на разстоянието към текущия + ръба от текущия към проверения. Цикълът завършва, когато флаговете на всички върхове станат равни на 1 или когато разстоянието до всички върхове с флаг 0 е безкрайно. Последният случай е възможен тогава и само ако графът е несвързан.

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

Вход: ОТ: масив от real – матрица от дължини на дъгите на графа; s е върхът, от който се търси най-краткият път, а t е върхът, до който се търси.

Изход: вектори T: масив от реални; и H: масив от 0..r. Ако отгоре vсе намира на най-краткия път от сда се T,тогава T[v]- дължина на най-късия път от сда се y; Добре] -непосредствено предшестващ пик припо най-краткия път.

H е масив, в който връх n съответства на връх m, предишният по пътя към n от s.

T е масив, в който връх n съответства на разстоянието от него до s.

X е масив, в който връх n съответства на 1, ако пътят до него е известен, и на 0, ако не.

инициализация на масива:

за vот 1 до Рнаправи

T[v]: = ∞ (неизвестен пряк път)

X[v]: = 0 (всички върхове са немаркирани)

H[s]: = 0 ( с нищо не идва преди това)

T[s]:= 0 (най-краткият път има дължина 0...)

X[s]:= 1 ( ...и той е познат ) v : = с (текущ топ)

М: (актуализация на бележките)

за и ∈ G( и) направи

ако X[i] = 0 & T[u]> T[v] + ° Стогава

т[у]: = T[v] + ° С(намерих по-кратък път от с в ипрез v }

h[u]:= v(запомни го)

м: = ∞

v : = 0

(намиране на края на най-краткия път)

за иот 1 до стр направи

ако X[u] = 0 &T[u]< Tтогава

v:= u;

м:= т[у]( Горна част v завършва най-късият път от с

ако v = 0 тогава

спри (няма изход с в T) край ако

ако v= Tтогава

стоп (намерен най-краткият път от с в T) край ако

X[v]: = 1 (намерен е най-краткият път от с в v ) отивам М

Обосновка

За да се докаже коректността на алгоритъма на Дейкстра, е достатъчно да се отбележи, че за всяко изпълнение на тялото на цикъла, започващо с етикета M, като vизползва се връх, за който е известен най-късият път от върха с.С други думи, ако X[v] = 1, тогава T[v] = d(s,v) , и всички върхове на пътя (s, v), дефиниран от вектора H, имат едно и също свойство, т.е.

Vu T[u] = 1 => T[u] = d(s,u)&T] = 1.

Наистина (по индукция), за първи път като vизползва се върха s, за който най-късият път е празен и има дължина 0 (непразните пътища не могат да бъдат по-къси, тъй като дължините на дъгите са неотрицателни). Нека T[u] = d(s,u) за всички предварително обозначени върхове и.Помислете за новомаркирания връх v, който се избира от условието T[v] = min T[u]. Имайте предвид, че ако пътят, минаващ през обозначените върхове, е известен, тогава е известен най-краткият път. Да приемем (напротив), че T[v] > d(s, v), тоест намереният път, водещ от св v,не е най-късият. Тогава трябва да има немаркирани върхове по този път. Помислете за първия връх wпо този път, така че T[w] = 0.Имаме: T[w] = d(s,w)⩽d(s>v)< Т[v],что противоречит выбору вершины u.

Времева сложност

Сложността на алгоритъма на Dijkstra зависи от това как да се намери непосетен връх с минимално разстояние до оригиналния, как да се съхрани наборът от непосетени върхове и как да се актуализират етикетите. Нека n е броят на върховете и нека m е броят на ръбовете в графа. След това, в най-простия случай, когато целият набор от върхове се претърсва, за да се намери върхът с минимално разстояние до оригиналния връх и се използва масив за съхраняване на разстоянията, времето за изпълнение на алгоритъма е O(n 2). Основният цикъл се изпълнява около n пъти, във всеки от тях се изразходват около n операции за намиране на минимума. Циклизирането през съседите на всеки посетен връх отнема брой операции, пропорционални на броя на ребрата m (тъй като всяко ребро се среща точно два пъти в тези цикли и изисква постоянен брой операции). По този начин общото време на работа на алгоритъма е O(n 2 +m), но тъй като m е много по-малко от n(n-1), то в крайна сметка е O(n 2).

За редки графи (т.е. тези, за които m е много по-малко от n²), непосетените върхове могат да се съхраняват в двоична купчина, а стойностите на разстоянието се използват като ключ. Тъй като цикълът се изпълнява около n пъти и броят на отпусканията (промените на етикета) не е повече от m, времето за изпълнение на такава реализация е O(nlogn+mlogn)

Пример

Изчисляване на разстояния от връх 1 по проходими върхове:

Помислете за примера за намиране на най-краткия път. Дадена е мрежа от магистрали, свързващи районите на града. Някои пътища са еднопосочни. Намерете най-кратките пътища от центъра на града до всеки град в района.

За да разрешите този проблем, можете да използвате Алгоритъмът на Дейкстра- алгоритъм върху графики, изобретен от холандския учен Е. Дейкстра през 1959 г. Намира най-късото разстояние от един от върховете на графиката до всички останали. Работи само за графики без ребра с отрицателно тегло.

Нека се изисква да се намерят най-късите разстояния от 1-ви връх до всички останали.

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

Етикетът на самия връх 1 се приема за 0, етикетите на останалите върхове са недостижими голямо число(в идеалния случай - безкрайност). Това отразява, че разстоянията от връх 1 до други върхове все още не са известни. Всички върхове на графа са маркирани като непосетени.

Първа стъпка

Връх 1 има минимален етикет.Върхове 2, 3 и 6 са неговите съседи.Заобикаляме съседите на върха на свой ред.

Първият съсед на връх 1 е връх 2, тъй като дължината на пътя до него е минимална. Дължината на пътя до него през връх 1 е равна на сумата от най-късото разстояние до връх 1, стойността на етикета му и дължината на ръба, преминаващ от 1-ви до 2-ри, тоест 0 + 7 = 7. Това е по-малко от текущия етикет на връх 2 (10000), така че новият етикет на втория връх е 7.


По същия начин намираме дължините на пътя за всички останали съседи (върхове 3 и 6).

Всички съседи на възел 1 са проверени. Текущото минимално разстояние до върха 1 се счита за окончателно и не подлежи на преразглеждане. Връх 1 е маркиран като посетен.

Втора стъпка

Стъпка 1 от алгоритъма се повтаря. Отново намираме „най-близкия“ от непосетените върхове. Това е връх 2, обозначен със 7.

Отново се опитваме да намалим етикетите на съседите на избрания връх, опитвайки се да преминем през тях през 2-рия връх. Съседите на връх 2 са върхове 1, 3 и 4.

Вертекс 1 вече е посетен. Следващият съсед на връх 2 е връх 3, тъй като има минималния етикет на върховете, отбелязани като непосетени. Ако отидете до него през 2, тогава дължината на такъв път ще бъде равна на 17 (7 + 10 = 17). Но текущият етикет на третия връх е 9 и 9< 17, поэтому метка не меняется.


Друг съсед на връх 2 е връх 4. Ако отидем до него през 2-ри, тогава дължината на такъв път ще бъде равна на 22 (7 + 15 = 22). От 22<10000, устанавливаем метку вершины 4 равной 22.

Всички съседи на връх 2 са разгледани, така че го маркираме като посетен.

Трета стъпка

Повтаряме стъпката от алгоритъма, като избираме връх 3. След неговата „обработка“ получаваме следните резултати.

Четвърта стъпка

Пета стъпка

шеста стъпка

Така най-краткият път от връх 1 до връх 5 ще бъде пътят през върховете 1 — 3 — 6 — 5 , тъй като по този начин качваме минимум 20.

Нека да разгледаме най-краткия път. Знаем дължината на пътя за всеки връх и сега ще разгледаме върховете от края. Помислете за крайния връх (в този случай, връх 5 ), и за всички върхове, с които е свързан, намираме дължината на пътя, като извадим теглото на съответното ребро от дължината на пътя на крайния връх.
Да, отгоре 5 има дължина на пътя 20 . Тя е свързана с върха 6 и 4 .
За върха 6 вземете теглото 20 - 9 = 11 (съвпадение).
За върха 4 вземете теглото 20 - 6 = 14 (не съвпада).
Ако в резултат получим стойност, която съответства на дължината на пътя на въпросния връх (в този случай връх 6 ), тогава именно от него е направен преходът към крайния връх. Маркираме този връх на желания път.
След това определяме ръба, през който стигнахме до върха 6 . И така докато стигнем до началото.
Ако в резултат на такова обхождане на някаква стъпка имаме еднакви стойности за няколко върха, тогава можем да вземем всеки от тях - няколко пътя ще имат еднаква дължина.

Реализация на алгоритъма на Дейкстра

За съхраняване на теглата на графиката се използва квадратна матрица. Върховете на графиката са в заглавията на редовете и колоните. А теглата на дъгите на графиката се поставят във вътрешните клетки на таблицата. Графиката не съдържа цикли, така че главният диагонал на матрицата съдържа нулеви стойности.

	1	2	3	4	5	6
1	0	7	9	0	0	14
2	7	0	10	15	0	0
3	9	10	0	11	0	2
4	0	15	11	0	6	0
5	0	0	0	6	0	9
6	14	0	2	0	9	0

Реализация в C++

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

#define _CRT_SECURE_NO_WARNINGS
#включи
#включи
#define РАЗМЕР 6
int main()
{
int a; // матрица на връзките
int d; // минимално разстояние
intv; // посетени върхове
int temp, miniindex, min;
int begin_index = 0;
система ("chcp 1251");
система ("cls");
// Инициализация на матрицата на връзката
за (int i = 0; i {
a[i][i] = 0;
за (int j = i + 1; j printf( „Въведете разстояние %d – %d:“, i + 1, j + 1);
scanf("%d" , &temp);
a[i][j] = температура;
a[j][i] = температура;
}
}
// Показване на матрицата на връзката
за (int i = 0; i {
за (int j = 0; j printf("%5d ", a[i][j]);
printf("\n");
}
//Инициализиране на върхове и разстояния
за (int i = 0; i {
d[i] = 10000;
v[i] = 1;
}
d=0;
// Стъпка на алгоритъма
направи(
минииндекс = 10000;
min = 10000;
за (int i = 0; i { // Ако върхът все още не е посетен и теглото е по-малко от min
if ((v[i] == 1) && (d[i] { // Преназначаване на стойности
min = d[i];
минииндекс=i;
}
}
// Добавете намереното минимално тегло
// към текущото тегло на върха
// и сравнете с текущото минимално тегло на върха
ако (minindex != 10000)
{
за (int i = 0; i {
ако (a[i] > 0)
{
температура = min + a[i];
ако (темп< d[i])
{
d[i] = температура;
}
}
}
v = 0;
}
) докато (minindex< 10000);
// Показване на най-късите разстояния до върховете
printf( "\nНай-къси разстояния до върховете: \n");
за (int i = 0; i printf("%5d ", d[i]);

// Възстановяване на пътя
инвертор; // масив от посетени върхове
int край = 4; // индекс на краен връх = 5 - 1
ver = край + 1; // начален елемент - краен връх
int k = 1; // индекс на предишния пик
int тегло = d; // тегло на крайния връх

докато (край != begin_index) // докато стигнем до началния връх
{
за (int i = 0; i // преглед на всички върхове
ако (a[i] != 0) // ако има връзка
{
int temp = тегло - a[i]; // определяне на теглото на пътя от предишния връх
ако (temp == d[i]) // ако теглото съвпада с изчисленото
{ // това означава, че е имало преход от този връх
тегло = температура; // съхранява новото тегло
край = i; // запазваме предишния връх
ver[k] = i + 1; // и го запишете в масив
k++;
}
}
}
// Показване на пътя (началният връх е в края на масива от k елемента)
printf( "\nИзходен най-кратък път\n");
за (int i = k - 1; i >= 0; i--)
printf("%3d ", ver[i]);
getchar(); getchar();
връщане 0;
}

Резултат от изпълнението


Обратно:

Даден е насочен или неориентиран претеглен граф с върхове и ръбове. Теглата на всички ребра са неотрицателни. Определен е някакъв начален връх. Изисква се да се намерят дължините на най-кратките пътища от връх до всички останали върхове, както и да се осигури начин за извеждане на самите най-кратки пътища.

Този проблем се нарича проблем за най-кратките пътища с един източник.

Алгоритъм

Това описва алгоритъма, предложен от холандския изследовател Дейкстра(Дийкстра) през 1959 г

Нека получим масив, в който за всеки връх ще съхраняваме текущата дължина на най-краткия път от до . Първоначално и за всички останали върхове тази дължина е равна на безкрайност (когато се прилага на компютър, обикновено се избира достатъчно голямо число като безкрайност, очевидно по-голямо от възможната дължина на пътя):

Освен това за всеки връх ще съхраняваме дали все още е етикетиран или не, т.е. нека получим булев масив. Първоначално всички върхове са немаркирани, т.е.

Самият алгоритъм на Дейкстра се състои от итерации. При следващата итерация се избира върхът с най-малка стойност сред тези, които все още не са етикетирани, т.е.:

(Ясно е, че при първата итерация ще бъде избран началният връх.)

Избраният по този начин връх се маркира маркиран. Освен това, при текущата итерация, от върха, релаксация: всички ръбове, излизащи от върха, се преглеждат и за всеки такъв връх алгоритъмът се опитва да подобри стойността на . Нека дължината на текущия ръб е , тогава под формата на код релаксацията изглежда така:

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

Струва си да се отбележи, че ако не всички върхове на графиката са достъпни от върха, тогава стойностите за тях ще останат безкрайни. Ясно е, че последните няколко итерации на алгоритъма просто ще изберат тези върхове, но тези итерации няма да произведат никаква полезна работа (тъй като едно безкрайно разстояние не може да отпусне други, дори безкрайни разстояния). Следователно, алгоритъмът може да бъде незабавно спрян, щом връх с безкрайно разстояние бъде взет като избран връх.

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

Остава да разберем как да изградим този масив от предци. Това обаче се прави много просто: при всяка успешна релаксация, т.е. когато от избрания връх има подобрение в разстоянието до някакъв връх, пишем, че предшественикът на върха е връхът:

Доказателство

Основно изявление, на който се основава коректността на алгоритъма на Дейкстра, е както следва. Твърди се, че след като всеки връх бъде маркиран, текущото разстояние до него вече е най-късото и съответно няма да се промени повече.

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

Помислете за най-краткия път до върха. Ясно е, че този път може да бъде разделен на два пътя: , състоящ се само от маркирани върхове (поне началният връх ще бъде в този път), и останалата част от пътя (може също да включва маркирани върхове, но винаги започва с неотбелязан). Означаваме с първия връх на пътя и с последния връх на пътя.

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

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

От друга страна, тъй като и двата и са немаркирани върхове, тъй като в текущата итерация беше избран върхът, а не върхът, получаваме друго неравенство:

От тези две неравенства заключаваме равенството , а след това от отношенията, намерени преди това, получаваме и:

Q.E.D.

Внедряване

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

Времето на работа на алгоритъма е сумата от:

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

Внедряване:

const int INF = 1000000000; int main() ( int n; ... четене на n ... вектор< vector < pair< int ,int >> > g(n); ... четене на графика... int s = ...; // начален връхвектор< int >d(n, INF), p(n); d[s] = 0; вектор< char >u(n); за (int i= 0; i< n; ++ i) { int v = - 1 ; for (int j= 0 ; j< n; ++ j) if (! u[ j] && (v == - 1 || d[ j] < d[ v] ) ) v = j; if (d[ v] == INF) break ; u[ v] = true ; for (size_t j= 0 ; j< g[ v] .size () ; ++ j) { int to = g[ v] [ j] .first , len = g[ v] [ j] .second ; if (d[ v] + len < d[ to] ) { d[ to] = d[ v] + len; p[ to] = v; } } } }

Тук графиката се съхранява под формата на списъци за съседство: за всеки връх списъкът съдържа списък с ръбове, произтичащи от този връх, т.е. списък от двойки >, където първият елемент на двойката е върхът, към който води ръбът, а вторият елемент е теглото на ръба.

5.4.3. Проблемът за най-краткия път и алгоритъмът на Дейкстра за решаването му

Нека е даден диграф Ж(V, д), на всяка дъга от които е присвоено число
Наречен дължината на дъгата.

Определение. Дължина path е сумата от дължините на дъгите, които изграждат този път. Проблем с най-краткия пътсложете така.

Опция 1.Намерете дължините на най-късите пътища (пътища с минимална дължина) и самите пътища от фиксиран връх скъм всички останали върхове на графа.

Вариант 2.Намерете дължините на най-късите пътища и самите пътища между всички двойки върхове в дадения граф.

Ако графиката има дъги с отрицателна дължина, проблемът може да няма решения (ще загуби смисъла си). Това се дължи на факта, че графиката може да съдържа контур с отрицателна дължина. Наличието на контури с отрицателна дължина означава, че дължината на пътя може да се направи равна на
. И ако няма контури с отрицателна дължина, тогава съществуват най-кратки пътища и всеки най-кратък път е проста верига.

Обърнете внимание, че ако съществува най-кратък път, тогава всеки от неговите подпътеки е и най-краткият път между съответните върхове.

Алгоритъмът на Дейкстра за решаване на проблема с най-краткия път.

Алгоритъмът работи с дъги с положителна дължина и определя най-кратките пътища от фиксиран връх скъм всички останали върхове на графа. Нека обозначим тези върхове v 1 , v 2 ,…, v н .

Определение.Нека извикаме върха uлежи по-близо до върха сотколкото отгоре vако дължината на най-късия път от спреди uпо-малко от дължината на най-късия път от спреди v. Ще кажем, че върховете uи v равноотдалечениот върха с, ако дължините на най-кратките пътища от спреди uи от спреди vсъвпада.

Алгоритъмът на Дейкстра подрежда последователно върховете на графика по отношение на близостта до върха си се основава на следните основни принципи.

Ако дължините на дъгата са положителни числа, тогава

най-близо до с върхът е самата тя. Дължината на най-късия път от спреди се 0;

най-близо до с връх, различен от с, лъжи от сна разстояние една дъга - най-късата от всички дъги, излизащи от върха с;

всеки междинен връх на най-краткия път от сдо някакъв връх vлежи по-близо до сотколкото крайния връх v;

най-краткият път до следващия подреден връх може да минава само през вече подредени върхове.

Нека алгоритъмът вече е подредил върховете v 1 , v 2 … v к . Означаваме с
,
дължина на най-късия път до върха v аз .

Разгледайте всички дъги на оригиналния график, които започват в един от върховете на множеството
и завършват на все още неподредени върхове. За всяка такава дъга напр
, изчислете сумата
. Тази сума е равна на дължината на пътя от с в г, в която вр v азе предпоследният връх, а пътят от с в v азе най-краткият от всички свързващи пътища с и v аз .

Това определя дължините на всички пътища от сдо все още неподредени върхове, в които са само върхове от междинните върхове кнай-близо до с. Нека най-късият от тези пътища завършва на върха w. Тогава wи яжте
близо до свръх.

Технически, действията съгласно алгоритъма на Дейкстра се извършват с помощта на апарата на върховите етикети. Етикет на върха vозначен като
. Всеки етикет е число, равно на дължината на някакъв път от с преди v. Етикетите са разделени на временни и постоянни. На всяка стъпка само един етикет става постоянен. Това означава, че стойността му е равна на дължината на най-късия път до съответния връх, а самият връх е подреден. Номерът на следващия подреден връх се отбелязва с буквата Р.

Описание на алгоритъма.

Етап 1. (Първоначална настройка). Слагам
и считайте този етикет за постоянен. Слагам
,
и третирайте тези етикети като временни. Слагам
.

Стъпка 2 (обща стъпка).Повтаря се н пъти, докато всички върхове на графа бъдат сортирани.

Преизчисляване на клеймо за време
всеки неподреден връх v аз, което включва дъгата, напускаща върха R,според правилото

Изберете върха с минимално времево клеймо. Ако има няколко такива върха, изберете всеки.

Позволявам w- върхът с минимално клеймо за време. Прочетете етикета
постоянен и поставен
.

Удобно е да подредите стъпките на алгоритъма на Дейкстра в таблица, всяка колона от която съответства на връх на графиката. Редовете на таблицата съответстват на повторението на общата стъпка.

Пример. За графиката на фиг. 4. намерете най-кратките пътища от върховете
към всички останали върхове на графа. Ръбовете означават две различно насочени дъги с еднаква дължина.

Решение.В табл. На всяка стъпка се записват 1 етикети на върховете. Постоянните знаци са отбелязани със знак "+". Нека опишем подробно как се изчисляват етикетите на върховете.

От връх 1 дъгите излизат към върхове 2, 5, 6. Преизчислете етикетите на тези върхове и попълнете втория ред на таблицата.

Етикетът на върха 6 става постоянен,
.

От връх 6, дъгите излизат към все още неподредени върхове 2, 5, 8, 9. Преизчислете техните времеви отпечатъци

Попълнете ред 3 от таблицата. Минимумът от времевите марки е 3 (етикет на върха 9),
.

От връх 9 дъгите излизат към все още неподредените върхове 5, 8, 11, 12. След това

Попълнете четвъртия ред на таблицата. В този ред два върха - 2 и 12 имат минимален времеви отпечатък равен на 4. Първо, нека подредим, например, връх 2. След това, на следващата стъпка, връх 12 ще бъде подреден.

маса 1

Така,
.

От връх 2 дъгите излизат към все още неподредените върхове 3, 4, 5. Преизчислете времевите клейма на тези върхове

Попълнете ред 5 от таблицата. Минимумът от времевите марки е 4 (етикет на върха 12),
.

Попълнете ред 6 от таблицата. Минимумът от клеймата за време е 5 (етикет на върха 5),
.

Попълнете ред 7 от таблицата. Етикетът на върха 8 става постоянен (равен е на 5),
.

Вертекс 11 е подреден.

От връх 11 дъгите излизат към неподредени върхове 7, 10. Преизчислете времевите клейма на тези върхове

Vertex 4 получава постоянен етикет.

От връх 4 дъгите излизат към неподредени върхове 3, 7. Преизчислете времевите клейма

Подредете горните 3.

Попълнете ред 12 от таблицата. На тази стъпка подреждаме последния неподреден връх 10.

Изграждане на дърво на най-кратките пътища.

Дървото с най-кратък път е насочено дърво с корен във връх. С . Всички пътища в това дърво са най-кратките пътища за тази графика.

Дървото на най-краткия път се изгражда според таблицата, връх по връх се включва в него в реда, в който са получили постоянни етикети. Коренът е първият възел, който се включва в дървото. С .

Нека изградим дърво на най-кратките пътища за нашия пример.

Първо включваме в дървото корена, връх 1. След това в дървото се включва дъгата (1,6). След това беше подреден връх 9, дължината на най-късия път до който е равна на 3. Първият път, когато числото 3 се появи в третия ред, който беше изпълнен с
. Следователно връх 6 е предпоследният връх на най-късия път до връх 9. Включваме дъгата (6,9) с дължина 1 в дървото.

След това връх 2 беше подреден с най-късата дължина на пътя, равна на 4. Това число се появи за първи път в третия ред, който беше изпълнен с
. Следователно най-късият път до втория връх минава по дъгата (6,2). Включваме дъгата (6,2) с дължина 2 в дървото.

След това беше нареден връх 12,
. Първият път, когато числото 4 се появява в четвъртия ред, който е попълнен, когато
. В дървото е включена дъгата (9,12) с дължина 1. Пълното дърво на най-кратките пътища е показано на фиг. 5.

Алгоритъмът на Дейкстра може да се провали, ако графиката има дъги с отрицателна дължина. И така, търсене на най-кратките пътища от върха с =1 за графиката на фиг. 6, алгоритъмът първо ще нареди възел 3, след това възел 2 и ще завърши. Освен това, този най-кратък път до връх 3, от гледна точка на алгоритъма на Дейкстра, е дъга (1,3) с дължина 3.

Всъщност най-краткият път до връх 3 се състои от дъги (1,2) и (2,3), дължината на този път е 5+(-3)=2.

Поради наличието на дъга (2,3) с отрицателна дължина –3 са нарушени следните основни принципи:

най-близо до с върхът лежи на разстояние две дъги от него, а не една;

междинният връх на най-късия път 1-2-3 (връх 2) се намира по-далеч от връх 1 (разстояние 5), отколкото крайният връх на път 3.

Следователно наличието на дъги с отрицателна дължина усложнява решението на задачата за най-краткия път и изисква използването на по-сложни алгоритми от алгоритъма на Дейкстра.

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

Например вземете следната насочена графика G:

Можем да представим тази графика като матрица C:

Нека вземем за източник връх 1. Това означава, че ще търсим най-кратките маршрути от връх 1 до върхове 2, 3, 4 и 5.
Този алгоритъм преминава стъпка по стъпка през всички върхове на графиката и им присвоява етикети, които са известното минимално разстояние от върха на източника до конкретен връх. Нека разгледаме този алгоритъм с пример.

Нека присвоим етикет равен на 0 на 1-ви връх, защото този връх е източникът. На останалите върхове ще бъдат присвоени етикети, равни на безкрайност.

След това избираме връх W, който има минимален етикет (сега това е връх 1) и разглеждаме всички върхове, до които от върха W има път, който не съдържа върхове-посредници. Присвояваме етикет на всеки от разглежданите върхове, равен на сумата от етикета W и дължината на пътищата от W до разглеждания връх, но само ако получената сума е по-малка от предишната стойност на етикета. Ако сумата не е по-малка, оставяме предишния етикет непроменен.

След като сме разгледали всички върхове, до които има директен път от W, маркираме върха W като посетен и избираме от непосетените този, който има минималната стойност на етикета, това ще бъде следващият връх W. В в този случай това е връх 2 или 5. Ако има няколко върха с еднакви етикети, тогава няма значение кой ще изберем като W.

Избираме връх 2. Но от него няма изходящ път, така че незабавно маркираме този връх като посетен и преминаваме към следващия връх с минималния етикет. Този път само връх 5 има минималния етикет. Помислете за всички върхове, до които има директни пътища от 5, но които все още не са маркирани като посетени. Отново намираме сумата от етикета на върха W и теглото на ръба от W до текущия връх и ако тази сума е по-малка от предишния етикет, тогава заместваме стойността на етикета с получената сума.

Въз основа на картината можем да видим, че етикетите на 3-ти и 4-ти връх са станали по-малки, тоест е намерен по-къс маршрут до тези върхове от изходния връх. След това маркирайте 5-ия връх като посетен и изберете следващия връх, който има минималния етикет. Повтаряме всички горни действия, докато има непосетени върхове.

След като изпълним всички стъпки, получаваме следния резултат:

Има и вектор P, въз основа на който можете да изградите най-кратките маршрути. По броя на елементите този вектор е равен на броя на върховете в графа.Всеки елемент съдържа последния междинен връх на най-късия път между изходния връх и крайния връх. В началото на алгоритъма всички елементи на вектора P са равни на изходния връх (в нашия случай P = (1, 1, 1, 1, 1)). Освен това, на етапа на преизчисляване на стойността на етикета за разглеждания връх, ако етикетът на разглеждания връх се промени на по-малък, записваме стойността на текущия връх W в масива P. Например: 3-тият връх имаше етикет със стойност "30", с W=1. Освен това, при W=5, етикетът на 3-тия връх се е променил на "20", следователно ще запишем стойността във вектора P - P=5. Също така, при W=5, стойността на етикета на 4-тия връх се е променила (беше "50", стана "40"), така че трябва да присвоите стойността W - P=5 на 4-тия елемент от вектор П. В резултат на това получаваме вектора Р = (1, 1, 5, 5, 1).

Знаейки, че всеки елемент от вектора P съдържа последния междинен връх на пътя между източника и крайния връх, можем да получим самия най-кратък маршрут.