Автор работы: Пользователь скрыл имя, 29 Декабря 2011 в 03:13, курсовая работа
В связи с этим актуальны исследования различных вопросов теории графов. В качестве темы нашей работы была выбрана тема нахождение наикратчайшего пути в графах.
Целью данной курсовой работы является практическая разработка алгоритма поиска кратчайших путей в графе, используя алгоритм Дейкстры, его последующая реализация на одном из языков программирования высокого уровня.
ВВЕДЕНИЕ 3
1. ТЕОРИЯ ГРАФОВ. 4
1.1. ИСТОРИЧЕСКАЯ СПРАВКА. 4
1.2. ОСНОВНЫЕ ТЕРМИНЫ И ТЕОРЕМЫ ТЕОРИИ ГРАФОВ. 10
2. ЗАДАЧИ НА ГРАФАХ. 13
2.1. ОПИСАНИЕ РАЗЛИЧНЫХ ЗАДАЧ НА ГРАФАХ. 13
2.2. НАХОЖДЕНИЕ КРОТЧАЙШИХ ПУТЕЙ В ГРАФЕ 14
2.3 АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ 15
Алгоритм Дейкстры 15
Алгоритм Джонсона 16
Алгоритм Флойда - Уоршелла 17
Алгоритм Беллмана - Форда 18
3.РЕШЕНИЕ ЗАДАЧИ «ВРУЧНУЮ» 20
4.ПРОГРАММА «ОПРЕДЕЛЕНИЕ КРАТЧАЙШЕГО ПУТИ В ГРАФЕ» 25
ЛИСТИНГ ПРОГРАММЫ 25
5.ПРИЛОЖЕНИЯ 27
6.ЗАКЛЮЧЕНИЕ 28
7. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 29