Алгоритм Флойда-Уоршела
Особливість знаходження найкоротшого шляху між кожною парою вершин у графі. Формалізація алгоритму Флойда-Уоршелла. Багатократне застосування алгоритму Дейкстри з послідовним вибором кожної вершини графу. Аналіз допущення наявності дуг з від’ємною вагою.
Подобные документы
Розробка програми для моделювання роботи алгоритму Дейкстри мовою C# з використанням об’єктно-орієнтованих принципів програмування. Алгоритм побудови робочого поля. Програмування графічного інтерфейсу користувача. Тестування програмного забезпечення.
курсовая работа, добавлен 06.08.2013Блок-схема алгоритма Флойда. Разработка его псевдокода в программе Microsoft Visual Studio. Программа реализации алгоритмов Беллмана-Форда. Анализ трудоемкости роста функции. Протокол тестирования правильности работы программы по алгоритму Флойда.
курсовая работа, добавлен 18.02.2013Розробка алгоритму та написання програми обчислення множин. Доведення теоретико-математичних тотожностей і тверджень. Побудова диз’юнктивної нормальної форми. Розробка алгоритму та написання програми знаходження множини елементарних циклів у графі.
курсовая работа, добавлен 17.04.2011Загальне значення графу. Алгоритми обходу графів. Матриця суміжності і список суміжності. Граф як структура даних. Використання двовимірного масиву чисел. Додавання нового зв'язку між заданою парою існуючих вершин, нової вершини разом з зв'язками.
отчет по практике, добавлен 29.06.2012Постановка задач линейного программирования. Примеры экономических задач, сводящихся к задачам линейного программирования. Допустимые и оптимальные решения. Алгоритм Флойда — алгоритм для нахождения кратчайших путей между любыми двумя узлами сети.
контрольная работа, добавлен 08.09.2010Визначення та способи представлення графів. Основні алгоритми на графах. Побудова мінімального остового дерева. Алгоритми Прима та Дейкстри. Модель Флойда-Уоршалла. Огляд можливостей мови програмування. Опис функцій програмної моделі, інтерфейс програми.
дипломная работа, добавлен 03.08.2014Методология и технология разработки программного продукта. Решение задачи поиска кратчайших путей между всеми парами пунктов назначения, используя алгоритм Флойда. Разработка интерфейса программы, с использованием среды Delphi Borland Developer Studio.
курсовая работа, добавлен 26.07.2014Корректность определения кратчайших путей в графе и рёбра отрицательной длины. Анализ алгоритмов Дейкстры, Беллмана-Форда, Флойда-Уоршелла. Вычисление кратчайших расстояний между всеми парами вершин графа. Топологическая сортировка ориентированного графа.
презентация, добавлен 19.10.2014Изучение основных понятий и определений теории графов. Рассмотрение методов нахождения кратчайших путей между фиксированными вершинами. Представление математического и программного обоснования алгоритма Флойда. Приведение примеров применения программы.
контрольная работа, добавлен 04.07.2011- 10. Машина Тюрінга
Алгоритм сортування методом простого вибору. Знаходження найдовшого шляху в графі. Синтез машини Тюрінга, що розмічає послідовність чисел. Порівняння алгоритмів між собою за часом виконання і займаної пам'яті. Алгоритм пошуку мінімального елементу.
курсовая работа, добавлен 17.05.2011 Програмна робота з графами: операції їх зчитування, збереження та обробки у вигляді перевірки на симетричність та орієнтованість. Основи пошуку в графі в різних напрямках. Розбиття множини вершин на класи еквівалентності за відношенням зв'язності графу.
лабораторная работа, добавлен 11.05.2011Засвоєння засобів аналізу трудомісткості обчислювальних алгоритмів. Побудова графа алгоритму з отриманої блок-схеми. Мінімізація графа, його подання у вигляді стохастичної матриці. Знаходження кількості звернень до файлів за допомогою Microsoft Excel.
лабораторная работа, добавлен 02.06.2011Сутність та зміст алгоритму Брезенхема для цифрових графопобудовувачів, сфери його застосування. Графік похибки в алгоритмі. Результати роботи покрокового циклу. Оцінка виконання покрокового алгоритму Брезенхема генерації кола, етапи його розв'язання.
реферат, добавлен 25.03.2011Основні теоретичні відомості про метод знаходження значення функції у міжвузловій точці за допомогою інтерполяційної формули Бесселя та приклад його застосування. Розробка алгоритму за даним методом. Опис програми, лістинг та результати тестування.
курсовая работа, добавлен 03.12.2009Понятие и основной принцип действия алгоритмов сортировки информации. Сравнительное исследование и анализ эффективности методов сортировки Шелла и Флойда в виде графиков зависимостей количества сравнений и числа перестановок элементов от объёма данных.
контрольная работа, добавлен 09.11.2010Алгоритмы нахождения кратчайшего пути: анализ при помощи математических объектов - графов. Оптимальный маршрут между двумя вершинами (алгоритм Декстры), всеми парами вершин (алгоритм Флойда), k-оптимальных маршрутов между двумя вершинами (алгоритм Йена).
курсовая работа, добавлен 16.01.2012Створення алгоритму програмної моделі розкладу в учбовому закладі для ефективного вирішення завдань автоматичного складання розкладу, шляхом підбору найбільш оптимальних варіантів. Шляхи реалізації розробленого алгоритму в середовищі Mathemetica 5.0.
дипломная работа, добавлен 25.10.2012Виділення інформаційних залежностей. Створення віртуальної декартової топології. Визначення розмірів об’єктів та введення вихідних даних. Масштабування та розподілення підзадач між процесам. Множення матричних блоків. Програмна реалізація алгоритму Фокса.
отчет по практике, добавлен 05.06.2015Теоретическое обоснование теории графов. Методы нахождения медиан графа. Задача оптимального размещения насосной станции для полива полей. Алгоритм Флойда, поиск суммарного расстояния до вершин. Функция нахождения индекса минимального значения в массиве.
курсовая работа, добавлен 28.05.2016Історія створення мови С#. Аналіз алгоритмів кодування даних. Розробка системи в середовищі Visual Studio 2008 Express. Схема шифрування алгоритму DES. Дослідження алгоритму RC2. Приклади хешів RIPEMD-160. Програмна реалізація основних процедур системи.
дипломная работа, добавлен 25.10.2012Визначення поняття алгоритма як набору інструкцій, які можна реалізувати чисто механічно, незалежно від розумових здібностей і можливостей виконавця. Словесний опис алгоритму сортування Шейкер та його роботи. Метод побудови одного найкоротшого покриття.
курсовая работа, добавлен 27.02.2012Алгоритм покриття за методом "мінімальній стовпець - максимальний рядок". Підпрограми основного алгоритму. Розробка програми сортування методом простих включень (бульбашковим методом). Словесний опис алгоритму, його контрольний приклад та ефективність.
курсовая работа, добавлен 06.03.2013Загальна характеристика застосування верстатів з числовим програмним управлінням. Разгляд етапів та особливостей складання керуючої програми. Вимоги до алгоритму розв’язку задачі. Побудова блок-схеми алгоритму. Опис програмного забезпечення, вибір мови.
курсовая работа, добавлен 24.05.2015Алгоритмы, использующие решение дополнительных подзадач. Основные определения теории графов. Поиск пути между парой вершин невзвешенного графа. Пути минимальной длины во взвешенном графе. Понятие кратчайшего пути для графов с помощью алгоритма Флойда.
реферат, добавлен 06.03.2010Створення алгоритму фрактального стиснення з втратами для зображень. Основні принципи методу, його обґрунтування та алгоритм реалізації. Характеристика типової схеми фрактального стиснення. Побудова алгоритму, його представлення та афінне перетворення.
курсовая работа, добавлен 10.07.2017