Алгоритмы дискретной математики - Курсовая работа

бесплатно 0
4.5 60
Определение кратчайших путей от вершины до остальных вершин графа, используя алгоритмы Дейкстры и Беллмана. Определение кратчайших путей между всеми парами вершин графа с применением алгоритма Флойда. Программирование алгоритма дискретной математики.

Скачать работу Скачать уникальную работу

Чтобы скачать работу, Вы должны пройти проверку:


Аннотация к работе
Министерство образования и науки РФ Сибирская государственная автомобильно-дорожная академия (СибАДИ) Факультет ИСУ Кафедра КИАС КУРСОВАЯ РАБОТА по дисциплине «Дискретная математика» на тему: «Алгоритмы дискретной математики» Выполнила: студентка группы ПИб-11И1 Окунев С.A. Проверила: доцент Палий И.А. Омск 2012 Содержание Задание 1 Алгоритм Дейкстры Задание 2 Алгоритм Беллмана Задание 3 Алгоритм Флойда Задание 4 Метод ветвей и границ 2. Задание по программированию Блок-схема программы Листинг программы Задание 1 Алгоритм Дейкстры Определить кратчайшие пути от вершины 1 до всех остальных вершин графа, используя алгоритм Дейкстры. Матрица 1 1 2 3 4 5 6 7 8 9 10 1 ? 6 ? ? ? ? ? 7 ? 1 2 3 ? 2 2 ? ? -1 ? ? 10 3 5 3 ? ? ? 2 ? ? 3 ? 4 ? 7 7 ? ? ? -2 2 ? ? 5 5 5 ? -2 ? 2 ? ? ? ? 6 7 5 ? ? ? ? 3 ? ? ? 7 ? ? ? ? 3 ? ? 5 2 3 8 ? ? ? ? ? 2 ? ? 10 9 9 ? 5 ? ? 10 ? 7 3 ? 7 10 ? ? ? 7 3 6 1 ? 8 ? Шаг 1: p = 1 d(1) = 0 Шаг 2: p = 10 d(2) = min(?; 0 6) = 6 d(8) = min(?; 0 7) = 7 d(10) = min(?; 0 1) = 1 Шаг 3: p = 7 d(4) = min(?; 1 7) = 8 d(5) = min(?; 1 3) = 4 d(6) = min(?; 1 6) = 7 d(7) = min(?; 1 1) = 2 d(9) = min(?; 1 8) = 9 Шаг 4: p = 5 d(5) = min(4; 2 3) = 4 d(8) = min(7; 2 5) = 7 d(9) = min(9; 2 2) = 4 Шаг 5: p = 9 d(2) = min(6; 5 4) = 6 d(4) = min(8; 4 2) = 6 d(4) = min(7; 4 2) = 6 d(9) = min(4; 4 ?) = 4 Шаг 6: p = 2 d(2) = min(6; 4 5) = 6 d(8) = min(7; 4 3) = 7 Шаг 7: p = 4 d(3) = min(?; 6 2) = 8 d(4) = min(6; 6 2) = 6 Шаг 8: p = 6 d(3) = min(8; 6 7) = 8 d(8) = min(7; 6 2) = 7 d(6) = min(6; 6 2) = 6 Шаг 9: p = 8 d(8) = min(7; 6 ?) = 7 Шаг 10: p = 3 d(3) = min(8; 7 ?) = 8 1 2 3 4 5 6 7 8 9 10 P 1 0 ? ? ? ? ? ? ? ? ? p=1 2 0 6 ? ? ? ? ? 7 ? 1 p=10 3 0 6 ? 8 4 7 2 7 9 1 p=7 4 0 6 ? 8 4 7 2 7 4 1 p=5 5 0 6 ? 6 4 6 2 7 4 1 p=9 6 0 6 ? 6 4 6 2 7 4 1 p=2 7 0 6 8 6 4 6 2 7 4 1 p=4 8 0 6 8 6 4 6 2 7 4 1 p=6 9 0 6 8 6 4 6 2 7 4 1 p=8 10 0 6 8 6 4 6 2 7 4 1 p=3 Дерево: Задание 2 Алгоритм Беллмана Определить кратчайшие пути от вершины 1 до всех остальных вершин графа, пользуясь алгоритмом Беллмана.

Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность
своей работы


Новые загруженные работы

Дисциплины научных работ





Хотите, перезвоним вам?