Главная
База знаний "Allbest"
Программирование, компьютеры и кибернетика
Кратчайшие пути. Алгоритмы их нахождения
Кратчайшие пути. Алгоритмы их нахождения
Алгоритмы нахождения кратчайшего пути: анализ при помощи математических объектов - графов. Оптимальный маршрут между двумя вершинами (алгоритм Декстры), всеми парами вершин (алгоритм Флойда), k-оптимальных маршрутов между двумя вершинами (алгоритм Йена).
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 16.01.2012 |
| Размер файла | 569,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ТЮМЕНСКОЙ ОБЛАСТИ
ТЮМЕНСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ МИРОВОЙ
ЭКОНОМИКИ, УПРАВЛЕНИЯ И ПРАВА
ФАКУЛЬТЕТ УПРАВЛЕНИЯ
Кафедра математики и информатики
Курсовая работа
по дисциплине: "Технологии программирования"
на тему: "Кратчайшие пути. Алгоритмы их нахождения"
Выполнил:
студент 481 группы
Батусов И.В.
Проверил:
старший преподаватель
Наурусова Г.А.
ТЮМЕНЬ 2010
Содержание
- Введение
- Глава 1. Анализ теоретического материала
- 1.1 Граф
- 1.2 Пути и маршруты
- 1.2.1 Волновой алгоритм
- 1.2.2 Алгоритм Дейкстры
- 1.2.3 Алгоритм Беллмана-Форда
- 1.2.4 Алгоритм Флойда - Уоршелла
- 1.2.5 Алгоритм Йена
- Глава 2. Разработка программы поиска кратчайших путей в графе
- 2.1 Постановка задачи
- 2.2 Технические задачи
- 2.3 Кодовая реализация
- Заключение
- Список использованной литературы
- Приложения
Введение
Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.
Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п.
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.
Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:
алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);
алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин);
алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами).
Объект курсовой работы: кратчайшие пути
Предмет работы: алгоритмы нахождения кратчайших путей.
Цель: с помощью программы Microsoft Visual Basic Express Edition разработать приложение, позволяющее искать кратчайшие пути в произвольном графе.
Задачи, решение которых необходимо для достижения поставленной цели:
1) Исследование графа
2) Обзор понятий: пути и маршруты; дать определение кратчайшего пути
3) Изучение алгоритмов поиска кратчайших путей
4) Постановка технической задачи для разработки программы поиска кратчайших путей
5) Разработка программы поиска кратчайших путей
Актуальность данной работы заключается в том, что часто бывает полезно и наглядно изображать некоторую ситуацию в виде графов. Графы встречаются во многих областях под разными названиями: "структуры" в гражданском строительстве, "сети" в электротехнике, "социограммы" в социологии и экономике, "молекулярные структуры" в химии, "дорожные карты", электрические или газовые "распределительные сети" и так далее. И по этому крайне важно уметь находить кратчайшие пути в графе.
Глава 1. Анализ теоретического материала
1.1 Граф
Граф G задается множеством точек или вершин x1, х2,,……, хn (которое обозначается через X) и множеством линий или ребер a1, а2……, аn (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (X, А).
Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом (рис.1.1 (а)). Если ребра не имеют ориентации, то граф называется неориентированным (рис.1.1 (6)). В случае когда G = (X, А) является ориентированным графом и мы хотим пренебречь направленностью дуг из множества А, то неориентированный граф, соответствующий G, будем обозначать как G = (X, А).
Далее, когда дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т.е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рис.1.1 (а) обозначение (х1, х2) относится к дуге а2, а (х2,, х1) - к дуге а2.
Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин X и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества X в X, а граф в этом случае обозначается парой G = (X, Г).
Для графа на рис.1.1 (а) имеем Г (x1) = {х2,, х5}, т.е. вершины х2 и х5 являются конечными вершинами дуг, у которых начальной вершиной является х1.
Г (x2) ={x1, x3},
Г (x3) ={x1},
Г (x4) =Ш-пустое множество,
Г (x5) ={x4}
Рис.1.1 (а) Ориентированный граф, (б) Неориентированный граф, (в) Смешанный граф.
В случае неориентированного графа или графа, содержащего и дуги, и неориентированные ребра (см., например, графы, изображенные на рис.1.1 (6) и 1.1 (в)), предполагается, что соответствие Г задает такой эквивалентный, ориентированный граф, который получается из исходного графа заменой каждого неориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Так, например, для графа, приведенного на рис.1.1 (6), имеем Г (х5) = {х1, х3,, x4},
Г (х1) = {х5} и т.д.
Поскольку Г (x1) представляет собой множество таких вершин xi Є Х, для которых в графе G существует дуга (хi, xj), то через Г-1 (xi) естественно обозначить множество вершин хk, для которых в G существует дуга (хk, xi). Отношение Г-1 (хi) принято называть обратным соответствием. Для графа, изображенного на рис 1.1 (а), имеем
Г-1 (x1) ={x2. x3},
Г-1 (x2) ={x1},
и т.д.
Вполне очевидно, что для неориентированного графа Г-1 (xi) = Г (хi) для всех х1 Є X.
Когда отображение Г действует не на одну вершину, а на множество вершин Хq = {х1, x2, …, хq}, то под Г (Хq) понимают объединение
Г (x1) U Г (x2) U…U Г (xq),
т.е. Г (Хq) является множеством таких вершин хi Є X, что для каждой из них существует дуга (хi, хj,) в G, где хi Є Хq. Для графа, приведенного на рис.1.1 (а), Г ({x2, х5}) = {х1, х3,, x4} и Г ({x1, х3}) = {х2,, х5, х1}
Отображение Г (Г (xi)) записывается как Г2 (xi). Аналогично "тройное" отображение Г (Г (Г (хi))) записывается как Г3 (xi) и т.д. Для графа, показанного на рис.1.1 (а), имеем:
Г2 (x1) = Г (Г (x1)) = Г ({х2,, x5}) = {х1, х3,, x4},
Г3 (x1) =Г (Г2 (x1)) =Г ({x1, x3, x4}) ={x1, x3, x5}
и т.д.
Аналогично понимаются обозначения Г-2 (хi), Г-3 (хi) и т. Д
1.2 Пути и маршруты
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Дуги, имеющие общие концевые вершины, называются смежными.
Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Очевидно, что простая орцепь является также орцепью, но обратное утверждение неверно. Маршрут есть неориентированный "двойник" пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Иногда дугам графа сопоставляются числа называемые весом, или длиной, или стоимостью (ценой) дуги. Тогда граф называется графом со взвешенными дугами. Иногда веса приписываются вершинам графа, и тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. Вес пути в графе определяется как сумма весов ребер этого пути. Кратчайшим путем между двумя вершинами называется путь наименьшего веса, соединяющий эти вершины.
Кратчайший путь можно найти с помощью следующих алгоритмов:
Волновой алгоритм
Алгоритм Дейкстры
Алгоритм Беллмана - Форда
Алгоритм Флойда - Уоршелла
Алгоритм Йена
Выбор алгоритма нахождения кратчайшего пути зависит от вида графа в котором требуется найти кратчайший путь.
1.2.1 Волновой алгоритм
Волновой алгоритм - алгоритм, позволяющий найти минимальный путь в графе с рёбрами единичной длины. Основан на алгоритме поиска в ширину. Применяется для нахождения кратчайшего пути в графе, в общем случае находит лишь его длину.
Суть алгоритма заключается в следующем. На двумерной клетчатой карте (матрице), состоящей из "проходимых" и "непроходимых" клеток, обозначена клетка старта и клетка финиша. Цель алгоритма - проложить кратчайший путь от клетки старта к клетке финиша, если это, конечно, возможно. От старта во все направления распространяется волна, причем каждая пройденная волной клетка помечается как "пройденная". Волна, в свою очередь, не может проходить через клетки помеченные как "пройденные" или "непроходимые". Волна движется, пока не достигнет точки финиша или пока не останется не пройденных клеток. Если волна прошла все доступные клетки, но так и не достигла клетку финиша, значит, путь от старта до финиша проложить невозможно. После достижения волной финиша, от старта прокладывается путь до финиша и сохраняется в массиве.
Волновой алгоритм состоит из двух этапов.
На первом этапе моделируется процесс распространения волны от ячейки А по свободным ячейкам ДРП (Дискретного Рабочего Поля).
При распространении волны от ячейки А, алгоритм последовательно строит f1 (А) - первый, f2 (А) - второй,., fk (А) - k-ый ее фронты. Если проведение пути возможно, то на k+1-ом шаге окажется, что ячейка В є Оk+1 (А). Если в следующий фронт не удается включить ни одной свободной ячейки, т.е. Оk (А) = Оk+1 (А), то при данных условиях путь провести невозможно.
Т.о. первый этап волнового алгоритма определяет возможность проведения пути между А и В.
На втором этапе, начиная с ячейки В, по определенным правилам, выполняется переход от ячейки k-ого фронта к ячейке k-1 фронта до ячейки А. Пройденные ячейки - искомый путь.
Условия, которые нужно выполнить для проведения пути и оценки его оптимальности должны быть заложены в правила, по которым движется фронт волны.
Распространение волны заключается в присваивании ячейкам, соседним с ячейкой предыдущего фронта, значения весовой функции. Вес ячейки k-ого фронта Pk является функцией веса ячейки k-1-ого фронта.
Метод кодирования ячеек по mod3 базируется на основном требовании к весам: Pk-1 ? Pk ? Pk+1. Ячейкам, включенным в последующие фронты, можно присваивать не сами веса, а их значения по mod3 (1,2,3,1,2,3,.). Проведение пути заключается в отслеживании отметок (1,2,3). Если ячейка имеет несколько соседних ячеек с одинаковыми метками, то используется правило приоритетных направлений.
При движении от ячейки В к ячейке А используется следующее правило приоритетов: <, ^, >, v.
1.2.2 Алгоритм Дейкстры
Алгоримтм Демйкстры (Dijkstra's algorithm) - алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных (если таковые имеются). Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.
алгоритм маршрут оптимальный вершина
В процессе работы алгоритма последовательно помечаются рассмотренные вершины графа. Причем вершина, помеченная последней (на данный момент) расположена ближе к исходной вершине, чем все непомеченные, но дальше, чем все помеченные.
Сначала помечается исходная вершина; следующей, очевидно, будет помечена вершина, ближайшая к исходной, и смежная с ней.
Пусть на каком-то шаге уже помечено несколько вершин. Известны кратчайшие пути, ведущие из исходной вершины к помеченным. Для каждой из непомеченных вершин проделаем следующее:
Рассмотрим все дуги, ведущие из помеченных вершин в одну непомеченную. Каждая такая дуга является последней дугой на пути из исходной вершины в эту непомеченную.
Выберем из этих путей кратчайший. А затем выберем среди них самый короткий ко всем непомеченным вершинам, и пометим вершину, к которой он ведет.
Алгоритм завершится, когда будут помечены все достижимые вершины.
В результате работы алгоритма Дейкстры строится Дерево кратчайших путей.
1.2.3 Алгоритм Беллмана-Форда
Алгоритм Беллмана - Форда применяется для нахождения кратчайшего расстояния от вершины [s] до остальных вершин. Одна из его ключевых особенностей, отличающая его от алгоритма Дейкстры, заключается в том, что он способен работать на графах, где вес ребер может быть задан отрицательным числом. Алгоритм может обнаруживать побочное явление таких графов - циклы отрицательной величины по которым можно вечно крутиться, уменьшая расстояние до вершин. Процесс не закончится. Поэтому, цикл проверки вершин ограничен числом N (числом самих вершин). Этого достаточно для того, чтобы просчитать минимальное расстояние до любой вершины, а главное алгоритм в любом случае завершится.
Так же особенностью алгоритма является то, что в одну и туже вершину мы можем попасть несколько раз.
1.2.4 Алгоритм Флойда - Уоршелла
Алгоритм Флойда - Уоршелла - динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа.
Процедура находит пути минимального веса в графе G= (V,E) заданном весовой матрицей W у которой элемент W [i, j] равен весу ребра соединяющего i-ую и j-ую вершины. При этом полагаем, что W [i, i] =0 для всех i. Путь ищется для всех пар вершин графа. Для бесконечности используется число GM его можно задавать в зависимости от конкретной задачи.
Следует заметить, что если в графе существует контур отрицательной сумарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, "прокрутившись" в контуре необходимое количество раз. Поэтому поставленная задача разрешима не всегда. В случае описанном выше, алгоритм Флойда прекращает свою работу. Останавливаясь подробнее надо заметить, что если граф неориентированный (W [i,j] - симметрична), то ребро с отрицательным весом является как раз таким контуром (туда-сюда можно бегать пока не сделаем вес достаточно малым)
Алгоритм Флойда предполагает последовательное преобразование матрицы весов W. В конечном итоге получаем матрицу, элементы d [i,j] которой представляют из себя вес минимального пути соединяющего i и j вершины.
На выходе получаем матрицу D минимальных весов и матрицу P при помощи которой можно восстановить путь минимального веса следующим образом: значение p [i,j] будет равно номеру последней вершины в пути между i и j. Переменная s на выходе равна 1, если алгоритм отработал полностью, и нулю, если в ходе работы алгоритма найден контур отрицательного веса.
1.2.5 Алгоритм Йена
Алгоритм предназначен для нахождения К путей минимальной длины во взвешенном графе соединяющих вершины u1,u2. Ищутся пути, которые не содержат петель.
Работа алгоритма начинается с нахождения кратчайшего пути, для этого будем использовать уже описанный алгоритм Дейкстры. Второй путь ищем перебирая кратчайшие отклонения от первого, третий кратчайшие отклонения от второго и т.д.
Пошаговое описание:
Найти минимальный путь P1= (v11,.,v1L [1]). Положить k = 2. Включить P1 в результирующий список.
Положить MinW равным бесконечности. Найти отклонение минимального веса, от (k-1) - го кратчайшего пути Pk-1 для всех i=1,2,.,L [k-1], выполняя для каждого i шаги с 3-го по 6-й.
Проверить, совпадает ли подпуть, образованный первыми i вершинами пути Pk-1, с подпутем, образованным первыми i вершинами любого из путей j=1,2,.,k-1). Если да, положить W [vk-1i,vji+1] равным бесконечности в противном случае ничего не изменять (чтобы в дальнейшем исключить получение в результат одних и тех же путей).
Используя алгоритм нахождения кратчайшего пути, найти пути от vk-1i к u2, исключая из рассмотрения корни (vk-11,.,vk-1i) (чтобы исключить петли), для этого достаточно положить равными бесконечности элементы столбцов и строк матрицы W, соответствующие вершинам входящим в корень.
Построить путь, объединяя корень и найденное кратчайшее ответвление, если его вес меньше MinW, то запомнить его.
Восстановить исходную матрицу весов W и возвратиться к шагу 3.
Поместить путь минимального веса (MinW), найденный в результате выполнения шагов с 3 по 6, в результирующий список. Если k = K, то алгоритм заканчивает работу, иначе увеличить k на единицу и вернуться к шагу 2.
Алгоритм использует массив p для результирующего списка путей, и массив l для хранения соответствующих длин, при этом если начиная с некоторого i элементы l [i] равны - 1, значит существует только i-1 кратчайших путей без петель.
Глава 2. Разработка программы поиска кратчайших путей в графе
2.1 Постановка задачи
С помощью программы Microsoft Visual Basic Express Edition разработать приложение, позволяющее находить кратчайшие пути в графе по алгоритму Флойда.
Осуществить:
· ввод произвольного графа с клавиатуры;
· поиск кратчайших путей;
· очистка полей вывода;
Создать удобный интерфейс, с отображением на форме результатов поиска кратчайших путей.
2.2 Технические задачи
1. Введение 1.1 Наименование программы Наименование программы: "Алгоритм Флойда" 1.2 Назначение и область применения Программа предназначена для нахождения кратчайших путей между всеми вершинами графа, которая обрабатывает следующие данные:
1.2.1 матрица достижимости 1.2.2 матрица весов ребер 1.2.3 вершину начала пути 1.2.4 вершину конца пути Программа предоставляет форму визуального представления введенных данных.
2. Требования к программе 2.1 Требования к функциональным характеристикам Программа должна обеспечивать возможность поиска конкретного кратчайшего пути и его веса.
3. Требования к программной документации 3.1 Предварительный состав программной документации Состав программной документации должен включать в себя:
3.1.1 техническое задание;
3.1.2 программный код;
3.1.3 визуальное представление программы.
4. Стадии и этапы разработки 4.2 Этапы разработки На стадии разработки технического задания должен быть выполнен этап разработки, согласования и утверждения настоящего технического задания.
На стадии рабочего проектирования должны быть выполнены перечисленные ниже этапы работ:
1. разработка программы;
2. разработка программного кода;
3. испытания программы.
На стадии внедрения должен быть выполнен этап разработки подготовка и передача программы.
2.3 Кодовая реализация
При запуске программы появляется форма, рисунок 1.
Рис.1.
При нажатии Файл >Новый граф, рисунок 2, программа запрашивает количество вершин графа для задания размерности массивов
Рис.2.
n = InputBox ("введите количество вершин графа") - 1
ReDim puti (n, n), graf (n, n), ves (n, n), dugi (n, n), vivod (n, n)
далее пользователь вводит матрицу достижимости и матрицу весов ребера, рисунок 3.
Рис.3.
For i = 0 To n
For j = 0 To n
If j = i Then
graf (i, j) = 0
ves (i, j) = o_O
Else
graf (i, j) = InputBox ("если вершина " & j + 1 & " достижима из вершины " & i + 1 & " то ставте 1, иначе оставте 0",, 0)
End If
If graf (i, j) = 1 Then
ves (i, j) = InputBox ("введите вес ребра" & i + 1 & "--" & j + 1 & " ")
Else: ves (i, j) = o_O
End If
которые выводятся на экран,рисунок 4.
Рис.4.
RichTextBox1. Text = RichTextBox1. Text & graf (i, j) & " "
If ves (i, j) = o_O Then RichTextBox2. Text = RichTextBox2. Text & "#" & " | " Else RichTextBox2. Text = RichTextBox2. Text & ves (i, j) & "|"
Next
RichTextBox1. Text = RichTextBox1. Text & vbCrLf
RichTextBox2. Text = RichTextBox2. Text & vbCrLf
Next
При нажатии Файл >Рассчитать пути,рисунок 5, программа копирует матрицу весов ребер и создает матрицу путей.
Рис.5.
For i = 0 To n
For j = 0 To n
dugi (i, j) = ves (i, j)
If ves (i, j) = o_O Then puti (i, j) = "#" Else puti (i, j) = j + 1
Next
Next
Далее проверяются все пути и кратчайшие запоминаются.
For i = 0 To n
For j = 0 To n
For k = 0 To n
If i <> j And dugi (j, i) <> o_O And i <> k And dugi (i, k) <> o_O And (dugi (j, k) = o_O Or dugi (j, k) > dugi (i, k) + dugi (j, i)) Then
puti (j, k) = puti (j, i) & puti (i, k)
dugi (j, k) = dugi (i, k) + dugi (j, i)
End If
Next
Next
Next
Полученные данные выводятся, рисунок 4.
Рис.4.
For i = 0 To n
For j = 0 To n
If puti (i, j) <> "#" Then puti (i, j) = i + 1 & puti (i, j)
If dugi (i, j) <> o_O Then vivod (i, j) = dugi (i, j) Else vivod (i, j) = "#"
Next
For j = 0 To n
RichTextBox3. Text = RichTextBox3. Text & vivod (i, j) & " | "
RichTextBox4. Text = RichTextBox4. Text & i & puti (i, j) & " | "
Next
RichTextBox3. Text = RichTextBox3. Text & vbCrLf
RichTextBox4. Text = RichTextBox4. Text & vbCrLf
Next
При нажатии Правка >Очистить, рисунок 5, оба поля очищаются
Рис.5.
RichTextBox1. Text = ""
RichTextBox2. Text = ""
RichTextBox3. Text = ""
RichTextBox4. Text = ""
TextBox1. Text = ""
TextBox2. Text = ""
TextBox3. Text = ""
TextBox4. Text = ""
Для того чтобы найти конкретный путь и его вес требуется ввести начало и конец в поля изображенные на рисунке 6 и нажать нопку "Найти путь"
Рис.5.
nach = TextBox1. Text
kon = TextBox2. Text
For i = 0 To n
For j = 0 To n
If i = nach - 1 And j = kon - 1 Then
TextBox3. Text = puti (i, j)
TextBox4. Text = vivod (i, j)
End If
Next
Next
Искомый путь и его вес будут выведены в соответствующих полях, рисунок 6.
Рис.6.
Заключение
В процессе выполнения данной курсовой работы, цель была достигнута, поставленные задачи выполнены.
В I главе была рассмотрена теория графов в общем, изучены понятия путей и маршрутов, подробно рассмотрены такие алгоритмы нахождения кратчайших путей в графе, как волновой алгоритм, алгоритм Дейкстры, алгоритм Белламна-Форда, алгоритм Флойда-Уоршелла и алгоритм Йена. Названные алгоритмы могут найти свое применение в программах для транспортных и коммуникационных сетей, таких как коммутация информационного пакета в Internet, где вершины - роутеры, а ребра это связи между роутерами. Таким образом, чем короче будет путь, тем быстрее пакет достигнет пункта назначения и меньше будут информационные потери.
Во II главе работы были реализованы поставленные задачи. С помощью Microsoft Visual Basic Express Edition был разработан программный продукт "Алгоритм Флойда" для нахождения кратчайших путей графа между всеми его вершинами. Преимуществом данной программы является то, что в ней реализованы принципы динамического программирования, то есть, пользователь сам определяет количество вершин графа, количество ребер (дуг) и их вес. В программе использован алгоритм Флойда - Уоршелла, который помогает последовательно вычислить все значения длин кратчайших путей между вершинами. На каждом шаге алгоритм генерирует две двумерные матрицы, одна из которых содержит длины кратчайших путей между всеми вершинами графа, а другая содержит сами пути.
Список использованной литературы
1. Касьянов В.Н., Евстигнеев В.А. "Графы в программировании: обработка, визуализация и применение", 2003, 1104с.
2. Кормен Т.М. "Алгоритмы. Построение и анализ", 2005, 1296с.
3. ru. wikipedia.org. Электронный ресурс
4. algolist. manual.ru. Электронный ресурс
5. comp-science. narod.ru. Электронный ресурс
6. dmtsoft.ru. Электронный ресурс
7. forum. sources.ru. Электронный ресурс
Приложения
Приложение 1
Тест программы
Используемый граф изображен на рисунке 7.
Рис.7.
Кратчайший путь между вершинами "1" и "5" пролегает через вершину "3". Вес этого пути "8".
Размещено на Allbest.ru
Подобные документы
Алгоритмы, использующие решение дополнительных подзадач. Основные определения теории графов. Поиск пути между парой вершин невзвешенного графа. Пути минимальной длины во взвешенном графе. Понятие кратчайшего пути для графов с помощью алгоритма Флойда.
реферат [39,6 K], добавлен 06.03.2010Разработка алгоритма реализации на ЭВМ процесса поиска кратчайшего пути в графе методом Дейкстры. Программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа. Проверка работоспособности программы на тестовых примерах.
реферат [929,8 K], добавлен 23.09.2013Блок-схема алгоритма Флойда. Разработка его псевдокода в программе Microsoft Visual Studio. Программа реализации алгоритмов Беллмана-Форда. Анализ трудоемкости роста функции. Протокол тестирования правильности работы программы по алгоритму Флойда.
курсовая работа [653,5 K], добавлен 18.02.2013Постановка задач линейного программирования. Примеры экономических задач, сводящихся к задачам линейного программирования. Допустимые и оптимальные решения. Алгоритм Флойда — алгоритм для нахождения кратчайших путей между любыми двумя узлами сети.
контрольная работа [691,8 K], добавлен 08.09.2010Изучение основных понятий и определений теории графов. Рассмотрение методов нахождения кратчайших путей между фиксированными вершинами. Представление математического и программного обоснования алгоритма Флойда. Приведение примеров применения программы.
контрольная работа [1,4 M], добавлен 04.07.2011Теория графов и её применения. Разработка программного продукта для решения задач нахождения минимального пути. Анализ надежности и качества ПП "метода Дейкстры". Математическая модель задачи. Алгоритмы Дейкстры на языке программирования Turbo Pascal.
курсовая работа [1,6 M], добавлен 26.03.2013Алгоритм поиска по первому наилучшему совпадению на графе. Основные классы для поиска пути в лабиринте. Тестирование нахождения кратчайшего пути в лабиринте. Порядок обхода вершин. Тестирование поведения программы при отсутствии пути в лабиринте.
курсовая работа [888,7 K], добавлен 19.12.2013Методология и технология разработки программного продукта. Решение задачи поиска кратчайших путей между всеми парами пунктов назначения, используя алгоритм Флойда. Разработка интерфейса программы, с использованием среды Delphi Borland Developer Studio.
курсовая работа [2,0 M], добавлен 26.07.2014Теоретическое обоснование теории графов. Методы нахождения медиан графа. Задача оптимального размещения насосной станции для полива полей. Алгоритм Флойда, поиск суммарного расстояния до вершин. Функция нахождения индекса минимального значения в массиве.
курсовая работа [336,8 K], добавлен 28.05.2016Алгоритм сортировки Шейкер: математическое описание задачи и описание алгоритма. Алгоритм покрытия: построение одного кратчайшего покрытия. Описание схемы и работы алгоритма на графах: нахождение кратчайшего пути. Контрольные примеры работы алгоритмов.
курсовая работа [43,8 K], добавлен 19.10.2010
