Решение задач на тему: Общие сведения о графах. Постановка задачи. Алгоритм Дейкстры

Введение

"Задача поиска кратчайшего пути" (задача о минимальном пути, задача о дилижансе), в последнее время получила широкое распространение, благодаря своему применению для решения множества других задач.

В настоящее время она применяется в алгоритмах поиска оптимального пути между двумя объектами (GPS-навигация), в системах автоматического пилотирования, для нахождения кратчайшего пути прохождения Internet-пакета по сети, и множества других.

Задача о кратчайшем пути является одной из важнейших классических задач теории графов. На сегодняшний день известно множество алгоритмов для ее решения.

Кратчайший путь рассматривается с помощью математической модели, называемой графом.

Оглавление

- Введение

- Общие сведения о графах

- Постановка задачи

- Алгоритм Дейкстры

- Алгоритм Беллмана-Форда

- Алгоритм А

- Практическое применение Заключение

- Список использованной литературы

- Приложения

Заключение

В данной курсовой работе была освещена задача поиска кратчайших путей на графе, а также рассмотрены 3 наиболее популярных алгоритма для ее решения. Были написаны программы, реализующие алгоритм Дейкстры, и алгоритм Форда-Беллмана.

Список литературы

1. Алексеев В.Е., Таланов В.А. - Графы. Модели вычислений. Структуры данных, Глава 3.4 Нахождение кратчайших путей в графе - Нижний Новгород, 2005;

2. Олифер В.Г. Олифер Н.А. - Основы компьютерных сетей - Питер, 2009;

3. "Глоссарий теории графов", <http://ru.wikipedia.org/Глоссарий_теории_графов>

. "Задача о кратчайшем пути", <http://ru.wikipedia.org/Задача_о_кратчайшем_пути;>

. "Алгоритм Дейкстры",<http://ru.wikipedia.org/Алгоритм_Дейкстры>