Определение кратчайших путей в транспортной сети на основе алгоритмов Дейкстры и Флойда.

Оглавление

Введение 2

Глава 1. Анализ методов и средств решения задачи 3

1.1 Общие сведения 3

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

1.3 Алгоритм Флойда 10

Глава 2. Построение моделей и алгоритмов 13

2.1 Общая модель разрабатываемого программного обеспечения 13

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

2.3 Алгоритм Флойда 15

Глава 3. Разработка программного обеспечения 18

3.1 Общие сведения 18

3.2 Выбор средств разработки 19

3.3 Реализация программного продукта 20

3.4 Контрольный пример работы 21

Заключение 23

Список использованных источников 24

Приложения 25

Приложение А. Листинг программы 25

Введение

Темой курсового проекта является «Определение кратчайших путей в транспортной сети на основе алгоритмов Дейкстры и Флойда». Курсовой проект ставит перед собой цель в нахождении кратчайших путей в транспортной сети на основе двух алгоритмов, применение которых широко распространено при решении логистических задач.

В теории графов сеть потоков (также известная как транспортная сеть) представляет собой ориентированный граф, в котором каждое ребро имеет емкость, а каждое ребро получает поток. Объем потока на кромке не может превышать емкость кромки. Часто в исследовании операций ориентированный граф называется сетью, вершины называются узлами, а ребра-дугами. Поток должен удовлетворять ограничению, что количество потока в узел равно количеству потока из него, если это не источник, который имеет только исходящий поток, или приемник, который имеет только входящий поток. Сеть может использоваться для моделирования трафика в дорожной системе, циркуляции с требованиями, жидкостей в трубах, токов в электрической цепи или чего-либо подобного, в котором что-то проходит через сеть узлов.

Объектом курсового проекта явлется граф – структура данных, которая используется в математической модели.

Предмет курсового проекта – алгоритмы Дейкстры и Флойда. Алгоритмы решают одну и ту же задачу но разными способами, имеют различную сложность в работе и потреблении памяти.

Для достижения поставленной цели планируется выполнение следующих шагов:

1. Провести анализ методов и средств решения задачи

2. Проанализировать алгоритм Дейкстры

3. Проанализировать алгоритм Флойда

4. Выполнить построение моделей и алгоритмоы

5. Составить общую модель разрабатываемого программного обеспечения

6. Провести моделирование алгоритма Дейкстры

7. Провести моделирование алгоритма Флойда

8. Разработать программное обеспечение:

 выбор средств разработки;

 реализация программного продукта;

 контрольный пример работы .

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