мо це число до позначки рядка і суму проставимо на колонку, в якому ця клітина знаходиться. Потім відобразимо позначки стовпців щодо головної діагоналі. Виникнуть помічені рядки. З кожною з помічених рядків проробимо те ж саме: переглянемо позначену рядок зліва направо і щоразу, зустрічаючи клітку з числом, додамо це число до позначки рядка і суму поставимо в якості позначки на колонку, в якому ця клітина варто. При цьому будемо дотримуватися принцип: «наявну позначку не змінювати». Потім позначки стовпців відобразимо щодо головної діагоналі і з поміченими рядками знову проробимо те ж саме. І так далі, поки не виявляться поміченими всі рядки і всі стовпці.
Крок 2. Переглянемо рядки таблиці в порядку зростання їх номерів. У кожному рядку проглядаються клітини зліва направо і всякий раз, коли зустрічається число, воно складається з позначкою рядки і сума порівнюється з позначкою стовпця, в якому знайдене число розташоване. Якщо сума виявилася меншою, ніж позначка стовпця, то ця позначка стовпця замінюється на згадану суму. Якщо ж сума виявилася більшою або рівною позначці, то нічого не змінюється. Після такого перегляду всіх рядків нові позначки стовпців відображаються щодо головної діагоналі і вся процедура повторюється. І так до тих пір поки не припиняться які б то не було зміни в позначках.
Крок 3. Тепер по позначкам можна побудувати найкоротші шляхи з першої вершини в усі інші. Фіксуємо довільну вершину k (k=2,3, ... p) і опишемо найкоротший шлях з першої вершини в вершину k. По-перше, довжина цього найкоротшого шляху дорівнює позначці л k, що стоїть на колонку номер k. По-друге, передостання вершина в найкоротшому шляху з першої вершини в вершину k знаходиться так: в стовпці номер k відшукуємо число, сума якого з позначкою рядки, в якій воно розташоване, дорівнює л k. Нехай номер рядка, в якій знайдене число виявилося, дорівнює l. Тоді передостанній вершиною в найкоротшому шляху з 1 в k буде вершина l. Вершину, яка передує вершині l, треба відшукувати як передостанню в найкоротшому шляху з 1 в l і так далі.
Таблиця 2.1. Позначення елементів.
№Обозначеніе елементів математичної моделіНаіменованіе елементів математичної моделі1GГраф2V Кількість вершин графа3EКолічество ребер графа
3. Розробка структури програми і алгоритмів програмних модулів і їх опис
Структура програми
Структура програми показана на рис. 3.1.
1
Рис. 3.1. Модульна структура програми.
Сполучення модулів
Сполучення модулів програми описана в таблиці 3.1.
Таблиця 3.1. Сполучення модулів.
НомерВходВиход1int n, int s - 2-bool
4. Рішення завдання на конкретному прикладі
Розглянемо на контрольному прикладі рішення задачі з вхідним файлом input.txt. У вхідному файлі будуть міститися кількість вершин у графі і матриця суміжності. Нескінченність буде позначатися 0.
Вхідний файл «input.txt» має вигляд:
8
10 13 0 0 0 0 0
0 0 0 0 0 11 0
0 0 17 10 0 0 0
0 17 0 0 16 12 0
0 10 0 0 11 0 15
0 0 16 11 0 15 10
11 0 12 0 15 0 0
0 0 0 15 10 0 0
. Прочитуємо кількість вершин.
. Прочитуємо і перевіряємо ваги ребер: якщо вага ребра більше 100000, або менше - 100 000, або не цифри виводимо помилку, якщо дорівнює 0 приписуємо значення 100000 (нескінченність).
. Вводимо початкову вершину і перевіряємо: якщо менше одиниці, або більше кількості вершин, або не цифри виводимо помилку і просимо повторити введення.
. Проходимо масив до тих пір, поки не знайдемо найкоротші відстані від початкової вершини:
Наведемо приклад. Нехай вихідний зважений граф дає наступну матрицю M:
Почнемо розставляти позначки:
Проведемо зменшення позначок:
. Виводимо найкоротші шляхи
? 2: 10;
? 3: 13;
? 4: 30;
? 5: 23;
? 6: 34;
? 7: 21;
? 8: 38;
Структура даних
lt; Кількість вершин gt;
lt; Вагомості ре...
