Готовая курсовая работа

Рассмотрим реализацию алгоритма Дейкстры.

Для реализации алгоритма поиска кратчайшего пути из вершины s в вершину t взвешенный граф, имеющий N вершин, представим в виде матрицы смежности вершин sm, причем если путь из вершины i в вершину j существует, элемент smij будет равен весу соответствующего ребра; если пути нет – бесконечности.

Отчет 18 с., 6 рис., 3 табл., 7 источников, 1 прил.

ГРАФ, ВЕРШИНА, РЕБРО, КРАТЧАЙШИЙ ПУТЬ В ГРАФЕ, МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО

Объектом исследования являются алгоритмы решения графовых задач.

Цель работы - разработка алгоритмического и программного обеспечения для решения задач поиска кратчайшего пути между вершинами графа и минимального остовного дерева графа.

В результате исследований были рассмотрены алгоритмы решения графовых задач.

Разработан программный продукт на языке программирования высокого уровня Delphi, реализующий алгоритм Дейкстры поиска кратчайшего пути между вершинами графа.

1. Алгоритм Дейкстры //Википедия. [Электронный ресурс]. Режим доступа: http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры

2. Алексеев В.Е., Таланов В.А. Графы и алгоритмы. //Интернет университет информационных технологий. [Электронный ресурс]. Режим доступа: http://www.intuit.ru/department/algorithms/gaa/15/

3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: Бином, 2000. – 960с.

4. Красиков И.В., Красикова И.Е. Алгоритмы – просто как дважды два. – М.: Эксмо, 2007. – 256с.

5. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2004. – 368с.

6. Поиск минимального покрывающего дерева в графе (алгоритм Прима). [Электронный ресурс]. Режим доступа: http://www.software.unn.ac.ru/cluster/cgi-bin/index.cgi?id=101&work=10&topic=0

7. Рыбаков Г. Минимальные остовные деревья. //Дискретная математика: алгоритмы. [Электронный ресурс]. Режим доступа: http://rain.ifmo.ru/cat/view.php/theory/graph-spanning-trees/mst-2005