>
. Кінцева вершина х2
Робочі дані:
. Масив distance [i]. У ньому будуть зберігається довжини найкоротших шляхів з x1 в i.
. Масив path [i]. У ньому буде зберігається крок найкоротшого шляху між i і х1.
. front [i]=1, якщо вершина у фронті хвилі, 0 інакше
. newfront [i] масив, де буде готується новий фронт.
Початок.
. Заповнюється масив distance значеннями 10000 (символізує нескінченність).
. front [x1]=1; інші елементи 0
. Обнуляємо всі елементи в newfront
Крок алгоритму.
. Шукаємо ненульові елементи front [i]. Для кожного такого front [i]!=0 робимо крок 1.1
.1 Шукаємо суміжні з i вершини, тобто шукаємо невід'ємні елементи W [i, j].
Для таких елементів робимо кроки 1.1.1-1.1.2
1.1.1 newdist=distance [i] + W [i, j]
1.1.2 якщо newdist
.1.2.1 distance [j]=newdist - тобто до j вершини існує шлях довжини newdist
.1.2.2 path [j]=i - тобто найкоротший шлях в j лежить через вершину i
.1.2.3 newfront [j]=1 - додаємо j вершину в новий фронт
. Аналізуємо newfront.
.1. Якщо newfront [x2]=1 (тобто в новому фронті присутній кінцева вершина), то шлях знайдений і переходимо до кроку 3
.2. Якщо newfront [i]=0 для всіх i то шляху між x1 і х2 не існує, завершуємо алгоритм.
.3. Інакше для всіх i front [i]=newfront [i]; newfront [i]=0; тобто оновлюємо фронт, і Обнуляємо новий фронт, і повторюємо крок 1.
. Крок 3. Роздруківка шляху. Мабуть найкоротший шлях з x1 в х2 знайдений.
Довжина цього шляху лежить в distance [x2].
Друкуємо шлях їх х2 в х1:
t=x2; (t!=x1)
{(x2);=path [t];
}
Отримали роздруківку найкоротшого шляху з х2 в х1, для виведення результату цей шлях записуємо в зворотному напрямку.
ОСОБЛИВОСТІ ПРОГРАМНОЇ РЕАЛІЗАЦІЇ
Вхідні дані: матриця суміжності, де нулями позначені відсутні дуги, а числа - ваги дуг з'єднують відповідні вершини. Негативних ваг бути не може. Матриця інцидентності задається у файлі testdata.xls, звідки згодом програма їх буде зчитувати. Обмежень на розмір матриці не накладає.
Виконання програми: алгоритм реалізований у середовищі Matlab у вигляді функції deikstra (initialPoint, endPoint), яка в якості аргументів приймає початкову та кінцеву точку для пошуку найкоротшого шляху між ними. Початкова і кінцева точки задаються за номером відповідної вершини графа.
Аналіз вхідних даних: так як негативні ваги неможливі, то на самому початку програма аналізує введені вхідні дані; при виявленні негативного ваги повертає помилку і завершує виконання.
Результат: виводиться в командне вікно у вигляді стовпчика, в якому зверху вниз написані номери вершин, через які...
