Зміст
Введення
Розробка блок-схеми алгоритмів
Розробка псевдокоду алгоритмів
Аналіз трудомісткості зростання функції
Програма реалізації алгоритмів
Тестування програм реалізації алгоритмів
.1 Тестування правильності
.2 Аналіз за часом
Аналіз результатів
Висновок
Список використаних джерел
Додаток А Код програми за алгоритмом Флойда
Додаток Б Код програми за алгоритмом Беллмана-Форда
Введення
Алгоритм Флойда пошуку найкоротших шляхів між усіма парами вершин.
Граф - це сукупність безлічі вершин і безлічі пар вершин (зв'язків між вершинами, дуг).
Алгоритм Флойда - Уоршелла - алгоритм для знаходження найкоротших відстаней між усіма вершинами зваженого графа без циклів з негативною вагою з використанням методу динамічного програмування.
Цей алгоритм був одночасно опубліковано в статтях Роберта Флойда (Robert Floyd <# "justify"> Для заданого зваженого графа G = (< i align = "justify"> V, E) алгоритм знаходить найкоротші шляхи із заданої вершини до всіх інших вершин . В, випадку, коли в графі містяться негативні цикли, досяжні з , алгоритм повідомляє, що найкоротших шляхів не існує.
1. Розробка блок-схеми алгоритмів
На малюнку 1 представлена ​​розроблена блок-схема алгоритму Флойда, де показано, яким чином, працює цей алгоритм. i, j, k , - аргументи проходу по циклу, N < span align = "justify"> - розмір масиву відстаней, D [N] [N] - масив відстаней.
В
Рисунок 1 - Блок-схема алгоритму Флойда
На малюнку 2 представлена ​​розроблена блок-схема алгоритму Беллмана-Форда, де показано, яким чином, працює цей алгоритм. Smej - матриця суміжності графа, start_v - початкова вершина, mRast - масив існуючих у графі дуг, rez - масив найкоротших відстаней, RELAX ( rez [mRast [ j ]. to] ) - поліпшення шляху між початковою і j-ой вершиною графа.
В
Рисунок 2 - Блок-схема алгоритму Беллмана-Форда
<...
