Курсовая на тему Разработка алгоритмического и программного обеспечения для решения графовых задач

Автор: Юлия

Тип работы: Курсовая

Предмет: Программирование

Страниц: 23

Год сдачи: 2009

ВУЗ, город: ОмГТУ

Выдержка

Рассмотрим реализацию алгоритма Дейкстры.
Для реализации алгоритма поиска кратчайшего пути из вершины 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