www.wikidata.uk-ua.nina.az

Алгоритм Дейкстри алгоритм на графах відкритий Дейкстрою Знаходить найкоротший шлях від однієї вершини графу до всіх інш

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

Алгоритм Дейкстри — алгоритм на графах, відкритий Дейкстрою. Знаходить найкоротший шлях від однієї вершини графу до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без ребер від'ємної довжини.

Алгоритм Дейкстри
Клас Алгоритм пошуку
Структура даних Граф
Найгірша швидкодія

Формулювання задачі Редагувати

Варіант 1. Дана мережа автомобільних доріг, що з'єднують міста Львівської області. Знайти найкоротшу відстань від Львова до кожного міста області, якщо рухатись можна тільки по дорогах.

Варіант 2. Дана карта велосипедних доріжок Латвії та Білорусі. Знайти мінімальну відстань, яку треба проїхати, щоб дістатися від Риги до Бобруйська.

Варіант 3. Є план міста з нанесеними на нього місцями розміщення пожежних частин. Знайти найближчу до кожного дому пожежну станцію.

Абстракція Редагувати

Дано неорієнтований зв'язний граф G(V, U). Знайти відстань від вершини a до всіх інших вершин V.

Інтуїтивне пояснення Редагувати

Зберігатимемо поточну мінімальну відстань до всіх вершин V (від даної вершини a) і на кожному кроці алгоритму намагатимемося зменшити цю відстань. Спочатку встановимо відстані до всіх вершин рівними нескінченості, а до вершини а — нулю. Розглянемо виконання алгоритму на прикладі. Хай потрібно знайти відстані від 1-ї вершини до всіх інших. Кружечками позначені вершини, лініями — шляхи між ними («дуги»). Над дугами позначена їх «ціна» — довжина шляху. Надписом над кружечком позначена поточна найкоротша відстань до вершини.

Крок 1 Редагувати

Ініціалізація. Відстань до всіх вершин графу V = . Відстань до а = 0. Жодної вершини графу ще не опрацьовано.

Крок 2 Редагувати

Знаходимо таку вершину (із ще не опрацьованих), поточна найкоротша відстань до якої мінімальна. В нашому випадку це вершина 1. Обходимо всіх її сусідів і, якщо шлях в сусідню вершину через 1 менший за поточний мінімальний шлях в цю сусідню вершину, то запам'ятовуємо цей новий, коротший шлях як поточний найкоротший шлях до сусіда.

Крок 3 Редагувати

Перший по порядку сусід 1-ї вершини — 2-а вершина. Шлях до неї через 1-у вершину дорівнює найкоротшій відстані до 1-ї вершини + довжина дуги між 1-ю та 2-ю вершиною, тобто 0 + 7 = 7. Це менше поточного найкоротшого шляху до 2-ї вершини, тому найкоротший шлях до 2-ї вершини дорівнює 7.

Кроки 4, 5 Редагувати

Аналогічну операцію проробляємо з двома іншими сусідами 1-ї вершини — 3-ю та 6-ю.

Крок 6 Редагувати

Всі сусіди вершини 1 перевірені. Поточна мінімальна відстань до вершини 1 вважається остаточною і обговоренню не підлягає (те, що це дійсно так, вперше довів Дейкстра). Тому викреслимо її з графу, щоб відмітити цей факт.

Крок 7 Редагувати

Практично відбувається повернення до кроку 2. Знову знаходимо «найближчу» необроблену (невикреслену) вершину. Це вершина 2 з поточною найкоротшою відстанню до неї = 7. І знову намагаємося зменшити відстань до всіх сусідів 2-ї вершини, намагаючись пройти в них через 2-у. Сусідами 2-ї вершини є 1, 3, 4.

Крок 8 Редагувати

Перший (по порядку) сусід вершини № 2 — 1-ша вершина. Але вона вже оброблена (або викреслена — див. крок 6). Тому з 1-ю вершиною нічого не робимо.

Крок 8 (з іншими вхідними даними) Редагувати

Інший сусід вершини 2 — вершина 4. Якщо йти в неї через 2-у, то шлях буде = найкоротша відстань до 2-ї + відстань між 2-ю і 4-ю вершинами = 7 + 15 = 22. Оскільки 22 < ∞, встановлюємо відстань до вершини № 4 рівним 22.

Крок 9 Редагувати

Ще один сусід вершини 2 — вершина 3. Якщо йти в неї через 2-у, то шлях буде = 7 + 10 = 17. Але 17 більше за відстань, що вже запам'ятали раніше до вершини № 3 і дорівнює 9, тому поточну відстань до 3-ї вершини не міняємо.

Крок 10 Редагувати

Всі сусіди вершини 2 переглянуті, заморожуємо відстань до неї і викреслюємо її з графу.

Кроки 11 — 15 Редагувати

По вже «відпрацьованій» схемі повторюємо кроки 2 — 6. Тепер «найближчою» виявляється вершина № 3. Після її «обробки» отримаємо такі результати:

Наступні кроки Редагувати

Проробляємо те саме з вершинами, що залишилися (№ по порядку: 6, 4 і 5).

Завершення виконання алгоритму Редагувати

Алгоритм закінчує роботу, коли викреслені всі вершини. Результат його роботи видно на останньому малюнку: найкоротший шлях від 1-ї вершини до 2-ї становить 7, до 3-ї — 9, до 4-ї — 20, до 5-ї — 20, до 6-ї — 11 умовних одиниць.

Найпростіша реалізація Редагувати

Найпростіша реалізація алгоритму Дейкстри потребує дій. У ній використовується масив відстаней та масив позначок. На початку алгоритму відстані заповнюються великим додатнім числом (більшим максимального можливого шляху в графі), а масив позначок заповнюється нулями. Потім відстань для початкової вершини вважається рівною нулю і запускається основний цикл.

На кожному кроці циклу ми шукаємо вершину з мінімальною відстанню і прапором рівним нулю. Потім ми встановлюємо в ній позначку 1 і перевіряємо всі сусідні з нею вершини. Якщо в ній відстань більша, ніж сума відстані до поточної вершини і довжини ребра, то зменшуємо його. Цикл завершується коли позначки всіх вершин стають рівними 1.

Реалізація програми пошук найкоротшого шляху алгоритмом Дейкстри Редагувати

Цей розділ потребує додаткових посилань на джерела для поліпшення його перевірності. Будь ласка, допоможіть удосконалити цей розділ, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки.
Матеріал без джерел може бути піддано сумніву та вилучено. (липень 2015)

Нижче наведено реалізацію програми мовою програмування С.

// Вершини неорієнтованого графа - це точки // Вага ребра неорієнтованого графа - це відстань. #include <stdio.h> int main() {  // КІЛЬКІСТЬ ТОЧОК  printf("Введіть кількість точок: ");  int kt = 0; // kt - кількість точок  scanf("%d", &kt);   // ВІДСТАНЬ  // масив[рядок][стовпець]  int MV[kt][kt], v = 0; // M_[] - масив, MV[]/v - відстань.  for(int r = 0; r < kt; r++) // r - рядок  {  MV[r][r] = 0; // головна діагональ  for(int c = r + 1; c < kt; c++) // с - стовпець  {  printf("Введіть відстань від точки [%d] до точки [%d]: ", r + 1, c + 1);  // (точка - 1) -> точка в коді  // (точка в коді + 1) -> точка  scanf("%d", &v);  MV[r][c] = v; // над головною діагоналлю  MV[c][r] = v; // під головною діагоналлю  }  }   // ТАБЛИЦЯ (ВІДСТАНЬ МІЖ ТОЧКАМИ) / МАТРИЦЯ СУМІЖНОСТІ  printf("Таблиця:\n[т]"); // [т] - точка  for(int c = 1; c <= kt; c++)  {  printf("[%d]", c);  }  printf("\n");  for(int r = 0; r < kt; r++)  {  printf("[%d]", r + 1);  for(int c = 0; c < kt; c++)  {  printf(" %d ", MV[r][c]);  }  printf("\n");  }   // "ТИПУ БЕСКІНЕЧНІСТЬ"  int b = 0; // b - "типу бескінечність" (сума відстаней між точками)  for(int r = 0; r < kt; r++)  {  for(int c = 0; c < kt; c++)  {  b += MV[r][c]; // b = b + MV[r][c]  }  }   // ПОЧАТКОВА ТОЧКА  printf("Введіть початкову точку: ");  int pt = 0; // pt - початкова точка  scanf("%d", &pt);   // МІНІМАЛЬНА ВІДСТАНЬ  int MMV[kt]; // MMV[] - мінімальна відстань від початкової точки [pt]  for(int x = 0; x < kt; x++)  {  MMV[x] = b; // мінімальна відстань до всіх точок - ∞  }  MMV[pt - 1] = 0; // мінімальна відстань початкової точки [pt] - 0  for(int x = 0; x < kt; x++)  {  printf("Початкова мінімальна відстань від початкової точки [%d] до точки [%d]: ", pt, x + 1);  if(MMV[x] == b)  {  printf("∞\n");  }  else  {  printf("%d\n", MMV[x]);  }  }   // ВІДВІДАНА ТОЧКА  int MVT[kt]; // MVT[] - відвідана точка  for(int x = 0; x < kt; x++)  {  MVT[x] = 0; // жодної точки ще не відвідано  }  printf("!!! ✕ - означає, що точка не відвідана\n");  printf("!!! ✓ - означає, що точка відвідана\n");  for(int x = 1; x <= kt; x++)  {  printf("Точка [%d]: ✕\n", x);  }   // АЛГОРИТМ ДЕЙКСТРИ  printf("\nАлгоритм Дейкстри:\n");  printf("1) Шукаємо мінімальну відстань від початкової точки [%d] до невідвіданої точки.\n", pt);  printf("2) Знаходимо відстань від початкової точки [%d] до обраної невідвіданої\n", pt);  printf("точки та від обраної невідвіданої точки до наступної невідвіданої точки.\n");  printf("Формула: [V] = [min_v] + [v]\n");  printf("[V] - це відстань від початкової точки до обраної невідвіданої точки\n");  printf("та від обраної невідвіданої точки до наступної невідвіданої точки.\n");  printf("[min_v] - це мінімальна відстань від початкової точки до обраної невідвіданої точки.\n");  printf("[v] - це відстань від обраної невідвіданої точки до наступної невідвіданої точки.\n");  printf("3) [MIN_V] - це мінімальна відстань від початкової точки до наступної невідвіданої точки.\n");  printf("Якщо знайдена відстань [V] меньше [MIN_V], то [MIN_V] буде дорівнювати [V].\n");  printf("Якщо знайдена відстань [V] більше або дорівнює [MIN_V], то [MIN_V] залишається без зміни.\n");  int t = 0, mv = 0; // t - точка, mv - мінімальна відстань.  for(int x = 0, k = 1; x < kt; x++, k++) // k - крок  {  printf("\n%d-Й КРОК\n", k);  printf("Мінімальна відстань від початкової точки [%d] до невідвіданої точки:\n", pt);  mv = b; // початкова мінімальна відстань - ∞  for(int x = 0; x < kt; x++)  {   if(MVT[x] == 0 && mv > MMV[x]) // шукаємо невідвідану точку з мінімальною відстаню  {  t = x;  mv = MMV[x];  }  }  for(int x = 0; x < kt; x++)  {  if(MVT[x] != 1) // точка повина бути невідвідана  {  printf("[%d] - [%d]: ", pt, x + 1);  if(MMV[x] == b) // якщо мінімальна відстань - ∞  {  printf("∞\n");  }  else  {  if(MMV[x] == mv) // якщо мінімальна відстань дорівнює знайденній мінімальній відстані   {  printf("%d ✓\n", MMV[x]);  }  else  {  printf("%d\n", MMV[x]);  }  }  }  }  if(k != kt) // кінцева точка не розглядається (не має сенсу)  {  printf("Відстань [V] і мінімальна відстань [MIN_V]:\n");  for(int x = 0; x < kt; x++)  {  if(MVT[x] == 0 && MV[t][x] != 0)  {  v = mv + MV[t][x];  printf("[V] = [%d] - [%d] - [%d] = %d + %d = %d\n", pt, t + 1, x + 1, mv, MV[t][x], v);  printf("[MIN_V] = [%d] - [%d] = ", pt, x + 1);  if(MMV[x] == b) // якщо мінімальна відстань - ∞  {  printf("∞\n");  }  else  {  printf("%d\n", MMV[x]);  }  if(v < MMV[x]) // якщо знайдена відстань [V] меньше [MIN_V]  {  printf("%d < ", v);  if(MMV[x] == b) // якщо мінімальна відстань - ∞  {  printf("∞");  }  else   {  printf("%d", MMV[x]);  }  printf(" → [V] < [MIN_V] → [MIN_V] = [V] → [MIN_V] = %d\n", v);  MMV[x] = v; // якщо знайдена відстань [V] меньше [MIN_V], то [MIN_V] буде дорівнювати [V]  }  else // якщо знайдена відстань [V] більше або дорівнює [MIN_V]  {  printf("%d ≥ %d", v, MMV[x]),  printf(" → [V] ≥ [MIN_V] → [MIN_V] = [MIN_V] → [MIN_V] = %d\n", MMV[x]);  }  }  }  printf("Звідси слідує:\n");  for(int x = 0; x < kt; x++)  {  printf("мінімальна відстань від початкової точки [%d] до точки [%d]: ", pt, x + 1);  if(MMV[x] == b) // якщо мінімальна відстань - ∞  {  printf("∞\n");  }  else  {  printf("%d\n", MMV[x]);  }  }  }  MVT[t] = 1; // точка відвідана  for(int x = 0; x < kt; x++)  {  printf("Точка [%d]: ", x + 1);  if(MVT[x] == 1) // якщо точка відвідана  {  printf("✓\n");  }  else // якщо точка не відвідана  {  printf("✕\n");  }  }  }   // РЕЗУЛЬТАТ  printf("\nРЕЗУЛЬТАТ:\nМінімальна відстань:");  for(int x = 0; x < kt; x++)  {  if(x != pt - 1) // початкова точка "відкидається"  {  printf("\n[%d] - [%d]: %d", pt, x + 1, MMV[x]);  }  }    // ШЛЯХ  int MS[kt], ct = 0, k = 0;  // MS[] - шлях від [ct] до [pt], ct - кінцева точка, k - кількість точок.  printf("\nШлях:");  for(int x = 1; x <= kt; x++)  {  if(x != pt) // початкова точка "відкидається"  {  ct = x;  MS[0] = ct;  mv = MMV[ct - 1];  k = 1;  printf("\n[%d] - [%d]:", pt, ct);  while(ct != pt)  {  for(int x = 0; x < kt; x++)  {  if(MV[ct - 1][x] != 0)  {  v = mv - MV[ct - 1][x];  if(MMV[x] == v)  {  mv = v; // mv = MMV[x]  ct = x + 1;  MS[k] = x + 1;  k++;  }  }  }  }  for(int x = k - 1; x >= 0; x--)  {  printf(" %d", MS[x]);  }  }  }  return 0; }

Консоль:

Введіть кількість точок: 6 Введіть відстань від точки [1] до точки [2]: 9 Введіть відстань від точки [1] до точки [3]: 3 Введіть відстань від точки [1] до точки [4]: 0 Введіть відстань від точки [1] до точки [5]: 0 Введіть відстань від точки [1] до точки [6]: 1 Введіть відстань від точки [2] до точки [3]: 0 Введіть відстань від точки [2] до точки [4]: 8 Введіть відстань від точки [2] до точки [5]: 0 Введіть відстань від точки [2] до точки [6]: 9 Введіть відстань від точки [3] до точки [4]: 0 Введіть відстань від точки [3] до точки [5]: 5 Введіть відстань від точки [3] до точки [6]: 4 Введіть відстань від точки [4] до точки [5]: 5 Введіть відстань від точки [4] до точки [6]: 2 Введіть відстань від точки [5] до точки [6]: 6 Таблиця: [т][1][2][3][4][5][6] [1] 0 9 3 0 0 1  [2] 9 0 0 8 0 9  [3] 3 0 0 0 5 4  [4] 0 8 0 0 5 2  [5] 0 0 5 5 0 6  [6] 1 9 4 2 6 0  Введіть початкову точку: 3 Початкова мінімальна відстань від початкової точки [3] до точки [1]: ∞ Початкова мінімальна відстань від початкової точки [3] до точки [2]: ∞ Початкова мінімальна відстань від початкової точки [3] до точки [3]: 0 Початкова мінімальна відстань від початкової точки [3] до точки [4]: ∞ Початкова мінімальна відстань від початкової точки [3] до точки [5]: ∞ Початкова мінімальна відстань від початкової точки [3] до точки [6]: ∞ !!! ✕ - означає, що точка не відвідана !!! ✓ - означає, що точка відвідана Точка [1]: ✕ Точка [2]: ✕ Точка [3]: ✕ Точка [4]: ✕ Точка [5]: ✕ Точка [6]: ✕ Алгоритм Дейкстри: 1) Шукаємо мінімальну відстань від початкової точки [3] до невідвіданої точки. 2) Знаходимо відстань від початкової точки [3] до обраної невідвіданої точки та від обраної невідвіданої точки до наступної невідвіданої точки. Формула: [V] = [min_v] + [v] [V] - це відстань від початкової точки до обраної невідвіданої точки та від обраної невідвіданої точки до наступної невідвіданої точки. [min_v] - це мінімальна відстань від початкової точки до обраної невідвіданої точки. [v] - це відстань від обраної невідвіданої точки до наступної невідвіданої точки. 3) [MIN_V] - це мінімальна відстань від початкової точки до наступної невідвіданої точки. Якщо знайдена відстань [V] меньше [MIN_V], то [MIN_V] буде дорівнювати [V]. Якщо знайдена відстань [V] більше або дорівнює [MIN_V], то [MIN_V] залишається без зміни. 1-Й КРОК Мінімальна відстань від початкової точки [3] до невідвіданої точки: [3] - [1]: ∞ [3] - [2]: ∞ [3] - [3]: 0 ✓ [3] - [4]: ∞ [3] - [5]: ∞ [3] - [6]: ∞ Відстань [V] і мінімальна відстань [MIN_V]: [V] = [3] - [3] - [1] = 0 + 3 = 3 [MIN_V] = [3] - [1] = ∞ 3 < ∞ → [V] < [MIN_V] → [MIN_V] = [V] → [MIN_V] = 3 [V] = [3] - [3] - [5] = 0 + 5 = 5 [MIN_V] = [3] - [5] = ∞ 5 < ∞ → [V] < [MIN_V] → [MIN_V] = [V] → [MIN_V] = 5 [V] = [3] - [3] - [6] = 0 + 4 = 4 [MIN_V] = [3] - [6] = ∞ 4 < ∞ → [V] < [MIN_V] → [MIN_V] = [V] → [MIN_V] = 4 Звідси слідує: мінімальна відстань від початкової точки [3] до точки [1]: 3 мінімальна відстань від початкової точки [3] до точки [2]: ∞ мінімальна відстань від початкової точки [3] до точки [3]: 0 мінімальна відстань від початкової точки [3] до точки [4]: ∞ мінімальна відстань від початкової точки [3] до точки [5]: 5 мінімальна відстань від початкової точки [3] до точки [6]: 4 Точка [1]: ✕ Точка [2]: ✕ Точка [3]: ✓ Точка [4]: ✕ Точка [5]: ✕ Точка [6]: ✕ 2-Й КРОК Мінімальна відстань від початкової точки [3] до невідвіданої точки: [3] - [1]: 3 ✓ [3] - [2]: ∞ [3] - [4]: ∞ [3] - [5]: 5 [3] - [6]: 4 Відстань [V] і мінімальна відстань [MIN_V]: [V] = [3] - [1] - [2] = 3 + 9 = 12 [MIN_V] = [3] - [2] = ∞ 12 < ∞ → [V] < [MIN_V] → [MIN_V] = [V] → [MIN_V] = 12 [V] = [3] - [1] - [6] = 3 + 1 = 4 [MIN_V] = [3] - [6] = 4 4 ≥ 4 → [V] ≥ [MIN_V] → [MIN_V] = [MIN_V] → [MIN_V] = 4 Звідси слідує: мінімальна відстань від початкової точки [3] до точки [1]: 3 мінімальна відстань від початкової точки [3] до точки [2]: 12 мінімальна відстань від початкової точки [3] до точки [3]: 0 мінімальна відстань від початкової точки [3] до точки [4]: ∞ мінімальна відстань від початкової точки [3] до точки [5]: 5 мінімальна відстань від початкової точки [3] до точки [6]: 4 Точка [1]: ✓ Точка [2]: ✕ Точка [3]: ✓ Точка [4]: ✕ Точка [5]: ✕ Точка [6]: ✕ 3-Й КРОК Мінімальна відстань від початкової точки [3] до невідвіданої точки: [3] - [2]: 12 [3] - [4]: ∞ [3] - [5]: 5 [3] - [6]: 4 ✓ Відстань [V] і мінімальна відстань [MIN_V]: [V] = [3] - [6] - [2] = 4 + 9 = 13 [MIN_V] = [3] - [2] = 12 13 ≥ 12 → [V] ≥ [MIN_V] → [MIN_V] = [MIN_V] → [MIN_V] = 12 [V] = [3] - [6] - [4] = 4 + 2 = 6 [MIN_V] = [3] - [4] = ∞ 6 < ∞ → [V] < [MIN_V] → [MIN_V] = [V] → [MIN_V] = 6 [V] = [3] - [6] - [5] = 4 + 6 = 10 [MIN_V] = [3] - [5] = 5 10 ≥ 5 → [V] ≥ [MIN_V] → [MIN_V] = [MIN_V] → [MIN_V] = 5 Звідси слідує: мінімальна відстань від початкової точки [3] до точки [1]: 3 мінімальна відстань від початкової точки [3] до точки [2]: 12 мінімальна відстань від початкової точки [3] до точки [3]: 0 мінімальна відстань від початкової точки [3] до точки [4]: 6 мінімальна відстань від початкової точки [3] до точки [5]: 5 мінімальна відстань від початкової точки [3] до точки [6]: 4 Точка [1]: ✓ Точка [2]: ✕ Точка [3]: ✓ Точка [4]: ✕ Точка [5]: ✕ Точка [6]: ✓ 4-Й КРОК Мінімальна відстань від початкової точки [3] до невідвіданої точки: [3] - [2]: 12 [3] - [4]: 6 [3] - [5]: 5 ✓ Відстань [V] і мінімальна відстань [MIN_V]: [V] = [3] - [5] - [4] = 5 + 5 = 10 [MIN_V] = [3] - [4] = 6 10 ≥ 6 → [V] ≥ [MIN_V] → [MIN_V] = [MIN_V] → [MIN_V] = 6 Звідси слідує: мінімальна відстань від початкової точки [3] до точки [1]: 3 мінімальна відстань від початкової точки [3] до точки [2]: 12 мінімальна відстань від початкової точки [3] до точки [3]: 0 мінімальна відстань від початкової точки [3] до точки [4]: 6 мінімальна відстань від початкової точки [3] до точки [5]: 5 мінімальна відстань від початкової точки [3] до точки [6]: 4 Точка [1]: ✓ Точка [2]: ✕ Точка [3]: ✓ Точка [4]: ✕ Точка [5]: ✓ Точка [6]: ✓ 5-Й КРОК Мінімальна відстань від початкової точки [3] до невідвіданої точки: [3] - [2]: 12 [3] - [4]: 6 ✓ Відстань [V] і мінімальна відстань [MIN_V]: [V] = [3] - [4] - [2] = 6 + 8 = 14 [MIN_V] = [3] - [2] = 12 14 ≥ 12 → [V] ≥ [MIN_V] → [MIN_V] = [MIN_V] → [MIN_V] = 12 Звідси слідує: мінімальна відстань від початкової точки [3] до точки [1]: 3 мінімальна відстань від початкової точки [3] до точки [2]: 12 мінімальна відстань від початкової точки [3] до точки [3]: 0 мінімальна відстань від початкової точки [3] до точки [4]: 6 мінімальна відстань від початкової точки [3] до точки [5]: 5 мінімальна відстань від початкової точки [3] до точки [6]: 4 Точка [1]: ✓ Точка [2]: ✕ Точка [3]: ✓ Точка [4]: ✓ Точка [5]: ✓ Точка [6]: ✓ 6-Й КРОК Мінімальна відстань від початкової точки [3] до невідвіданої точки: [3] - [2]: 12 ✓ Точка [1]: ✓ Точка [2]: ✓ Точка [3]: ✓ Точка [4]: ✓ Точка [5]: ✓ Точка [6]: ✓ РЕЗУЛЬТАТ: Мінімальна відстань: [3] - [1]: 3 [3] - [2]: 12 [3] - [4]: 6 [3] - [5]: 5 [3] - [6]: 4 Шлях: [3] - [1]: 3 1 [3] - [2]: 3 1 2 [3] - [4]: 3 1 6 4 [3] - [5]: 3 5 [3] - [6]: 3 1 6

У математичних термінах Редагувати

Нехай u — вершина, від якої шукаються відстані, V — множина вершин графу, di — відстань від вершини u до вершини i, , w(i, j) — вага «ребра» (i, j).

Алгоритм:

1. Множина вершин U, до яких відстань відома, встановлюється рівною {u}.

2. Якщо U=V, алгоритм завершено.

3. Потенційні відстані Di до вершин з V\U встановлюються нескінченними.

4. Для всіх ребер (i, j), де i∈U та j∈V\U, якщо Dj>di+w(i, j), то Dj присвоюється di+w(i, j).

5. Шукається i∈V\U, при якому Di мінімальне.

6. Якщо Di дорівнює нескінченності, алгоритм завершено. В іншому випадку di присвоюється значення Di, U присвоюється U∪{i} і виконується перехід до кроку 2.

Див. також Редагувати

Посилання Редагувати

Вікісховище має мультимедійні дані за темою: Алгоритм Дейкстри


Це незавершена стаття про алгоритми.
Ви можете допомогти проєкту, виправивши або дописавши її.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Algoritm Dejkstri algoritm na grafah vidkritij Dejkstroyu Znahodit najkorotshij shlyah vid odniyeyi vershini grafu do vsih inshih vershin Klasichnij algoritm Dejkstri pracyuye tilki dlya grafiv bez reber vid yemnoyi dovzhini Algoritm DejkstriKlas Algoritm poshukuStruktura danih GrafNajgirsha shvidkodiya O E V log V displaystyle O E V log V Zmist 1 Formulyuvannya zadachi 2 Abstrakciya 3 Intuyitivne poyasnennya 3 1 Krok 1 3 2 Krok 2 3 3 Krok 3 3 4 Kroki 4 5 3 5 Krok 6 3 6 Krok 7 3 7 Krok 8 3 8 Krok 8 z inshimi vhidnimi danimi 3 9 Krok 9 3 10 Krok 10 3 11 Kroki 11 15 3 12 Nastupni kroki 3 13 Zavershennya vikonannya algoritmu 4 Najprostisha realizaciya 5 Realizaciya programi poshuk najkorotshogo shlyahu algoritmom Dejkstri 6 U matematichnih terminah 7 Div takozh 8 PosilannyaFormulyuvannya zadachi RedaguvatiVariant 1 Dana merezha avtomobilnih dorig sho z yednuyut mista Lvivskoyi oblasti Znajti najkorotshu vidstan vid Lvova do kozhnogo mista oblasti yaksho ruhatis mozhna tilki po dorogah Variant 2 Dana karta velosipednih dorizhok Latviyi ta Bilorusi Znajti minimalnu vidstan yaku treba proyihati shob distatisya vid Rigi do Bobrujska Variant 3 Ye plan mista z nanesenimi na nogo miscyami rozmishennya pozhezhnih chastin Znajti najblizhchu do kozhnogo domu pozhezhnu stanciyu Abstrakciya RedaguvatiDano neoriyentovanij zv yaznij graf G V U Znajti vidstan vid vershini a do vsih inshih vershin V Intuyitivne poyasnennya RedaguvatiZberigatimemo potochnu minimalnu vidstan do vsih vershin V vid danoyi vershini a i na kozhnomu kroci algoritmu namagatimemosya zmenshiti cyu vidstan Spochatku vstanovimo vidstani do vsih vershin rivnimi neskinchenosti a do vershini a nulyu nbsp Rozglyanemo vikonannya algoritmu na prikladi Haj potribno znajti vidstani vid 1 yi vershini do vsih inshih Kruzhechkami poznacheni vershini liniyami shlyahi mizh nimi dugi Nad dugami poznachena yih cina dovzhina shlyahu Nadpisom nad kruzhechkom poznachena potochna najkorotsha vidstan do vershini Krok 1 Redaguvati Inicializaciya Vidstan do vsih vershin grafu V displaystyle infty nbsp Vidstan do a 0 Zhodnoyi vershini grafu she ne opracovano nbsp Krok 2 Redaguvati Znahodimo taku vershinu iz she ne opracovanih potochna najkorotsha vidstan do yakoyi minimalna V nashomu vipadku ce vershina 1 Obhodimo vsih yiyi susidiv i yaksho shlyah v susidnyu vershinu cherez 1 menshij za potochnij minimalnij shlyah v cyu susidnyu vershinu to zapam yatovuyemo cej novij korotshij shlyah yak potochnij najkorotshij shlyah do susida nbsp Krok 3 Redaguvati Pershij po poryadku susid 1 yi vershini 2 a vershina Shlyah do neyi cherez 1 u vershinu dorivnyuye najkorotshij vidstani do 1 yi vershini dovzhina dugi mizh 1 yu ta 2 yu vershinoyu tobto 0 7 7 Ce menshe potochnogo najkorotshogo shlyahu do 2 yi vershini tomu najkorotshij shlyah do 2 yi vershini dorivnyuye 7 nbsp Kroki 4 5 Redaguvati Analogichnu operaciyu proroblyayemo z dvoma inshimi susidami 1 yi vershini 3 yu ta 6 yu nbsp nbsp Krok 6 Redaguvati Vsi susidi vershini 1 perevireni Potochna minimalna vidstan do vershini 1 vvazhayetsya ostatochnoyu i obgovorennyu ne pidlyagaye te sho ce dijsno tak vpershe doviv Dejkstra Tomu vikreslimo yiyi z grafu shob vidmititi cej fakt nbsp Krok 7 Redaguvati Praktichno vidbuvayetsya povernennya do kroku 2 Znovu znahodimo najblizhchu neobroblenu nevikreslenu vershinu Ce vershina 2 z potochnoyu najkorotshoyu vidstannyu do neyi 7 nbsp I znovu namagayemosya zmenshiti vidstan do vsih susidiv 2 yi vershini namagayuchis projti v nih cherez 2 u Susidami 2 yi vershini ye 1 3 4 Krok 8 Redaguvati Pershij po poryadku susid vershini 2 1 sha vershina Ale vona vzhe obroblena abo vikreslena div krok 6 Tomu z 1 yu vershinoyu nichogo ne robimo Krok 8 z inshimi vhidnimi danimi Redaguvati Inshij susid vershini 2 vershina 4 Yaksho jti v neyi cherez 2 u to shlyah bude najkorotsha vidstan do 2 yi vidstan mizh 2 yu i 4 yu vershinami 7 15 22 Oskilki 22 lt vstanovlyuyemo vidstan do vershini 4 rivnim 22 nbsp Krok 9 Redaguvati She odin susid vershini 2 vershina 3 Yaksho jti v neyi cherez 2 u to shlyah bude 7 10 17 Ale 17 bilshe za vidstan sho vzhe zapam yatali ranishe do vershini 3 i dorivnyuye 9 tomu potochnu vidstan do 3 yi vershini ne minyayemo nbsp Krok 10 Redaguvati Vsi susidi vershini 2 pereglyanuti zamorozhuyemo vidstan do neyi i vikreslyuyemo yiyi z grafu nbsp Kroki 11 15 Redaguvati Po vzhe vidpracovanij shemi povtoryuyemo kroki 2 6 Teper najblizhchoyu viyavlyayetsya vershina 3 Pislya yiyi obrobki otrimayemo taki rezultati nbsp Nastupni kroki Redaguvati Proroblyayemo te same z vershinami sho zalishilisya po poryadku 6 4 i 5 nbsp nbsp nbsp Zavershennya vikonannya algoritmu Redaguvati Algoritm zakinchuye robotu koli vikresleni vsi vershini Rezultat jogo roboti vidno na ostannomu malyunku najkorotshij shlyah vid 1 yi vershini do 2 yi stanovit 7 do 3 yi 9 do 4 yi 20 do 5 yi 20 do 6 yi 11 umovnih odinic Najprostisha realizaciya RedaguvatiNajprostisha realizaciya algoritmu Dejkstri potrebuye O V 2 displaystyle O V 2 nbsp dij U nij vikoristovuyetsya masiv vidstanej ta masiv poznachok Na pochatku algoritmu vidstani zapovnyuyutsya velikim dodatnim chislom bilshim maksimalnogo mozhlivogo shlyahu v grafi a masiv poznachok zapovnyuyetsya nulyami Potim vidstan dlya pochatkovoyi vershini vvazhayetsya rivnoyu nulyu i zapuskayetsya osnovnij cikl Na kozhnomu kroci ciklu mi shukayemo vershinu z minimalnoyu vidstannyu i praporom rivnim nulyu Potim mi vstanovlyuyemo v nij poznachku 1 i pereviryayemo vsi susidni z neyu vershini Yaksho v nij vidstan bilsha nizh suma vidstani do potochnoyi vershini i dovzhini rebra to zmenshuyemo jogo Cikl zavershuyetsya koli poznachki vsih vershin stayut rivnimi 1 Realizaciya programi poshuk najkorotshogo shlyahu algoritmom Dejkstri RedaguvatiCej rozdil potrebuye dodatkovih posilan na dzherela dlya polipshennya jogo perevirnosti Bud laska dopomozhit udoskonaliti cej rozdil dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno lipen 2015 Nizhche navedeno realizaciyu programi movoyu programuvannya S Vershini neoriyentovanogo grafa ce tochki Vaga rebra neoriyentovanogo grafa ce vidstan include lt stdio h gt int main KILKIST TOChOK printf Vvedit kilkist tochok int kt 0 kt kilkist tochok scanf d amp kt VIDSTAN masiv ryadok stovpec int MV kt kt v 0 M masiv MV v vidstan for int r 0 r lt kt r r ryadok MV r r 0 golovna diagonal for int c r 1 c lt kt c s stovpec printf Vvedit vidstan vid tochki d do tochki d r 1 c 1 tochka 1 gt tochka v kodi tochka v kodi 1 gt tochka scanf d amp v MV r c v nad golovnoyu diagonallyu MV c r v pid golovnoyu diagonallyu TABLICYa VIDSTAN MIZh TOChKAMI MATRICYa SUMIZhNOSTI printf Tablicya n t t tochka for int c 1 c lt kt c printf d c printf n for int r 0 r lt kt r printf d r 1 for int c 0 c lt kt c printf d MV r c printf n TIPU BESKINEChNIST int b 0 b tipu beskinechnist suma vidstanej mizh tochkami for int r 0 r lt kt r for int c 0 c lt kt c b MV r c b b MV r c POChATKOVA TOChKA printf Vvedit pochatkovu tochku int pt 0 pt pochatkova tochka scanf d amp pt MINIMALNA VIDSTAN int MMV kt MMV minimalna vidstan vid pochatkovoyi tochki pt for int x 0 x lt kt x MMV x b minimalna vidstan do vsih tochok MMV pt 1 0 minimalna vidstan pochatkovoyi tochki pt 0 for int x 0 x lt kt x printf Pochatkova minimalna vidstan vid pochatkovoyi tochki d do tochki d pt x 1 if MMV x b printf n else printf d n MMV x VIDVIDANA TOChKA int MVT kt MVT vidvidana tochka for int x 0 x lt kt x MVT x 0 zhodnoyi tochki she ne vidvidano printf oznachaye sho tochka ne vidvidana n printf oznachaye sho tochka vidvidana n for int x 1 x lt kt x printf Tochka d n x ALGORITM DEJKSTRI printf n Algoritm Dejkstri n printf 1 Shukayemo minimalnu vidstan vid pochatkovoyi tochki d do nevidvidanoyi tochki n pt printf 2 Znahodimo vidstan vid pochatkovoyi tochki d do obranoyi nevidvidanoyi n pt printf tochki ta vid obranoyi nevidvidanoyi tochki do nastupnoyi nevidvidanoyi tochki n printf Formula V min v v n printf V ce vidstan vid pochatkovoyi tochki do obranoyi nevidvidanoyi tochki n printf ta vid obranoyi nevidvidanoyi tochki do nastupnoyi nevidvidanoyi tochki n printf min v ce minimalna vidstan vid pochatkovoyi tochki do obranoyi nevidvidanoyi tochki n printf v ce vidstan vid obranoyi nevidvidanoyi tochki do nastupnoyi nevidvidanoyi tochki n printf 3 MIN V ce minimalna vidstan vid pochatkovoyi tochki do nastupnoyi nevidvidanoyi tochki n printf Yaksho znajdena vidstan V menshe MIN V to MIN V bude dorivnyuvati V n printf Yaksho znajdena vidstan V bilshe abo dorivnyuye MIN V to MIN V zalishayetsya bez zmini n int t 0 mv 0 t tochka mv minimalna vidstan for int x 0 k 1 x lt kt x k k krok printf n d J KROK n k printf Minimalna vidstan vid pochatkovoyi tochki d do nevidvidanoyi tochki n pt mv b pochatkova minimalna vidstan for int x 0 x lt kt x if MVT x 0 amp amp mv gt MMV x shukayemo nevidvidanu tochku z minimalnoyu vidstanyu t x mv MMV x for int x 0 x lt kt x if MVT x 1 tochka povina buti nevidvidana printf d d pt x 1 if MMV x b yaksho minimalna vidstan printf n else if MMV x mv yaksho minimalna vidstan dorivnyuye znajdennij minimalnij vidstani printf d n MMV x else printf d n MMV x if k kt kinceva tochka ne rozglyadayetsya ne maye sensu printf Vidstan V i minimalna vidstan MIN V n for int x 0 x lt kt x if MVT x 0 amp amp MV t x 0 v mv MV t x printf V d d d d d d n pt t 1 x 1 mv MV t x v printf MIN V d d pt x 1 if MMV x b yaksho minimalna vidstan printf n else printf d n MMV x if v lt MMV x yaksho znajdena vidstan V menshe MIN V printf d lt v if MMV x b yaksho minimalna vidstan printf else printf d MMV x printf V lt MIN V MIN V V MIN V d n v MMV x v yaksho znajdena vidstan V menshe MIN V to MIN V bude dorivnyuvati V else yaksho znajdena vidstan V bilshe abo dorivnyuye MIN V printf d d v MMV x printf V MIN V MIN V MIN V MIN V d n MMV x printf Zvidsi sliduye n for int x 0 x lt kt x printf minimalna vidstan vid pochatkovoyi tochki d do tochki d pt x 1 if MMV x b yaksho minimalna vidstan printf n else printf d n MMV x MVT t 1 tochka vidvidana for int x 0 x lt kt x printf Tochka d x 1 if MVT x 1 yaksho tochka vidvidana printf n else yaksho tochka ne vidvidana printf n REZULTAT printf n REZULTAT n Minimalna vidstan for int x 0 x lt kt x if x pt 1 pochatkova tochka vidkidayetsya printf n d d d pt x 1 MMV x ShLYaH int MS kt ct 0 k 0 MS shlyah vid ct do pt ct kinceva tochka k kilkist tochok printf n Shlyah for int x 1 x lt kt x if x pt pochatkova tochka vidkidayetsya ct x MS 0 ct mv MMV ct 1 k 1 printf n d d pt ct while ct pt for int x 0 x lt kt x if MV ct 1 x 0 v mv MV ct 1 x if MMV x v mv v mv MMV x ct x 1 MS k x 1 k for int x k 1 x gt 0 x printf d MS x return 0 Konsol Vvedit kilkist tochok 6 Vvedit vidstan vid tochki 1 do tochki 2 9 Vvedit vidstan vid tochki 1 do tochki 3 3 Vvedit vidstan vid tochki 1 do tochki 4 0 Vvedit vidstan vid tochki 1 do tochki 5 0 Vvedit vidstan vid tochki 1 do tochki 6 1 Vvedit vidstan vid tochki 2 do tochki 3 0 Vvedit vidstan vid tochki 2 do tochki 4 8 Vvedit vidstan vid tochki 2 do tochki 5 0 Vvedit vidstan vid tochki 2 do tochki 6 9 Vvedit vidstan vid tochki 3 do tochki 4 0 Vvedit vidstan vid tochki 3 do tochki 5 5 Vvedit vidstan vid tochki 3 do tochki 6 4 Vvedit vidstan vid tochki 4 do tochki 5 5 Vvedit vidstan vid tochki 4 do tochki 6 2 Vvedit vidstan vid tochki 5 do tochki 6 6 Tablicya t 1 2 3 4 5 6 1 0 9 3 0 0 1 2 9 0 0 8 0 9 3 3 0 0 0 5 4 4 0 8 0 0 5 2 5 0 0 5 5 0 6 6 1 9 4 2 6 0 Vvedit pochatkovu tochku 3 Pochatkova minimalna vidstan vid pochatkovoyi tochki 3 do tochki 1 Pochatkova minimalna vidstan vid pochatkovoyi tochki 3 do tochki 2 Pochatkova minimalna vidstan vid pochatkovoyi tochki 3 do tochki 3 0 Pochatkova minimalna vidstan vid pochatkovoyi tochki 3 do tochki 4 Pochatkova minimalna vidstan vid pochatkovoyi tochki 3 do tochki 5 Pochatkova minimalna vidstan vid pochatkovoyi tochki 3 do tochki 6 oznachaye sho tochka ne vidvidana oznachaye sho tochka vidvidana Tochka 1 Tochka 2 Tochka 3 Tochka 4 Tochka 5 Tochka 6 Algoritm Dejkstri 1 Shukayemo minimalnu vidstan vid pochatkovoyi tochki 3 do nevidvidanoyi tochki 2 Znahodimo vidstan vid pochatkovoyi tochki 3 do obranoyi nevidvidanoyi tochki ta vid obranoyi nevidvidanoyi tochki do nastupnoyi nevidvidanoyi tochki Formula V min v v V ce vidstan vid pochatkovoyi tochki do obranoyi nevidvidanoyi tochki ta vid obranoyi nevidvidanoyi tochki do nastupnoyi nevidvidanoyi tochki min v ce minimalna vidstan vid pochatkovoyi tochki do obranoyi nevidvidanoyi tochki v ce vidstan vid obranoyi nevidvidanoyi tochki do nastupnoyi nevidvidanoyi tochki 3 MIN V ce minimalna vidstan vid pochatkovoyi tochki do nastupnoyi nevidvidanoyi tochki Yaksho znajdena vidstan V menshe MIN V to MIN V bude dorivnyuvati V Yaksho znajdena vidstan V bilshe abo dorivnyuye MIN V to MIN V zalishayetsya bez zmini 1 J KROK Minimalna vidstan vid pochatkovoyi tochki 3 do nevidvidanoyi tochki 3 1 3 2 3 3 0 3 4 3 5 3 6 Vidstan V i minimalna vidstan MIN V V 3 3 1 0 3 3 MIN V 3 1 3 lt V lt MIN V MIN V V MIN V 3 V 3 3 5 0 5 5 MIN V 3 5 5 lt V lt MIN V MIN V V MIN V 5 V 3 3 6 0 4 4 MIN V 3 6 4 lt V lt MIN V MIN V V MIN V 4 Zvidsi sliduye minimalna vidstan vid pochatkovoyi tochki 3 do tochki 1 3 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 2 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 3 0 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 4 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 5 5 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 6 4 Tochka 1 Tochka 2 Tochka 3 Tochka 4 Tochka 5 Tochka 6 2 J KROK Minimalna vidstan vid pochatkovoyi tochki 3 do nevidvidanoyi tochki 3 1 3 3 2 3 4 3 5 5 3 6 4 Vidstan V i minimalna vidstan MIN V V 3 1 2 3 9 12 MIN V 3 2 12 lt V lt MIN V MIN V V MIN V 12 V 3 1 6 3 1 4 MIN V 3 6 4 4 4 V MIN V MIN V MIN V MIN V 4 Zvidsi sliduye minimalna vidstan vid pochatkovoyi tochki 3 do tochki 1 3 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 2 12 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 3 0 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 4 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 5 5 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 6 4 Tochka 1 Tochka 2 Tochka 3 Tochka 4 Tochka 5 Tochka 6 3 J KROK Minimalna vidstan vid pochatkovoyi tochki 3 do nevidvidanoyi tochki 3 2 12 3 4 3 5 5 3 6 4 Vidstan V i minimalna vidstan MIN V V 3 6 2 4 9 13 MIN V 3 2 12 13 12 V MIN V MIN V MIN V MIN V 12 V 3 6 4 4 2 6 MIN V 3 4 6 lt V lt MIN V MIN V V MIN V 6 V 3 6 5 4 6 10 MIN V 3 5 5 10 5 V MIN V MIN V MIN V MIN V 5 Zvidsi sliduye minimalna vidstan vid pochatkovoyi tochki 3 do tochki 1 3 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 2 12 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 3 0 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 4 6 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 5 5 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 6 4 Tochka 1 Tochka 2 Tochka 3 Tochka 4 Tochka 5 Tochka 6 4 J KROK Minimalna vidstan vid pochatkovoyi tochki 3 do nevidvidanoyi tochki 3 2 12 3 4 6 3 5 5 Vidstan V i minimalna vidstan MIN V V 3 5 4 5 5 10 MIN V 3 4 6 10 6 V MIN V MIN V MIN V MIN V 6 Zvidsi sliduye minimalna vidstan vid pochatkovoyi tochki 3 do tochki 1 3 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 2 12 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 3 0 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 4 6 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 5 5 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 6 4 Tochka 1 Tochka 2 Tochka 3 Tochka 4 Tochka 5 Tochka 6 5 J KROK Minimalna vidstan vid pochatkovoyi tochki 3 do nevidvidanoyi tochki 3 2 12 3 4 6 Vidstan V i minimalna vidstan MIN V V 3 4 2 6 8 14 MIN V 3 2 12 14 12 V MIN V MIN V MIN V MIN V 12 Zvidsi sliduye minimalna vidstan vid pochatkovoyi tochki 3 do tochki 1 3 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 2 12 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 3 0 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 4 6 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 5 5 minimalna vidstan vid pochatkovoyi tochki 3 do tochki 6 4 Tochka 1 Tochka 2 Tochka 3 Tochka 4 Tochka 5 Tochka 6 6 J KROK Minimalna vidstan vid pochatkovoyi tochki 3 do nevidvidanoyi tochki 3 2 12 Tochka 1 Tochka 2 Tochka 3 Tochka 4 Tochka 5 Tochka 6 REZULTAT Minimalna vidstan 3 1 3 3 2 12 3 4 6 3 5 5 3 6 4 Shlyah 3 1 3 1 3 2 3 1 2 3 4 3 1 6 4 3 5 3 5 3 6 3 1 6U matematichnih terminah RedaguvatiNehaj u vershina vid yakoyi shukayutsya vidstani V mnozhina vershin grafu di vidstan vid vershini u do vershini i w i j vaga rebra i j Algoritm 1 Mnozhina vershin U do yakih vidstan vidoma vstanovlyuyetsya rivnoyu u 2 Yaksho U V algoritm zaversheno 3 Potencijni vidstani Di do vershin z V U vstanovlyuyutsya neskinchennimi 4 Dlya vsih reber i j de i U ta j V U yaksho Dj gt di w i j to Dj prisvoyuyetsya di w i j 5 Shukayetsya i V U pri yakomu Di minimalne 6 Yaksho Di dorivnyuye neskinchennosti algoritm zaversheno V inshomu vipadku di prisvoyuyetsya znachennya Di U prisvoyuyetsya U i i vikonuyetsya perehid do kroku 2 Div takozh RedaguvatiZadacha komivoyazhera Algoritm poshuku A Posilannya RedaguvatiVikishovishe maye multimedijni dani za temoyu Algoritm DejkstriPoyaslennya algoritmu Dejkstri Arhivovano 9 lipnya 2021 u Wayback Machine na kanali Computerphile na YouTube angl algolist manual ru Arhivovano 5 grudnya 2006 u Wayback Machine Opis kod animaciya na sajti universitetu Oklanda angl C Anisimov Kak postroit kratchajshij marshrut mezhdu dvumya tochkami Arhivovano 26 listopada 2010 u Wayback Machine Realizaciya prostejshego varianta algoritma Dejkstry na e maxx ru Arhivovano 20 serpnya 2010 u Wayback Machine Realizaciya varianta algoritma Dejkstry dlya razrezhennyh grafov na e maxx ru Arhivovano 20 serpnya 2010 u Wayback Machine Realizaciya na osnove ocheredi s prioritetami na C Arhivovano 26 serpnya 2010 u Wayback Machine Realizaciya na osnove ocheredi s prioritetami na Java Arhivovano 11 lyutogo 2011 u Wayback Machine Algoritm Dejkstri z prikladami mathros net ua nbsp Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org w index php title Algoritm Dejkstri amp oldid 40595207