Поиск всех кратчайших путей в графе
Общие сведения о графах. Реализация алгоритма Флойда. Графы и способы их представления. Пути и циклы в графах. Программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа. Пример применения алгоритма Флойда на практике.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 19.11.2011 |
| Размер файла | 2,9 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Тема
«Поиск всех кратчайших путей в графе»
ЗАДАНИЕ
1. Изучить алгоритм Флойда для поиска всех кратчайших путей в графе.
2. Написать и отладить программу, реализующую разработанный алгоритм.
3. Проверить работоспособность программы на тестовых примерах.
1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
1.1 Постановка задачи и сфера ее применения
Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.
Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п.
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.
Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:
1. алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);
2. алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин);
3. алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами).
Основной задачей данной курсовой работы является программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа.
Программа должна работать так, чтобы пользователь вводил количество вершин и длины рёбер графа, а после обработки этих данных на экран выводился кратчайший путь между двумя заданными вершинами и его длина. Необходимо предусмотреть различные исходы поиска, чтобы программа не выдавала ошибок и работала правильно.
Данная программа может использоваться в дискретной математике для исследования графов или в качестве наглядного пособия, демонстрирующего применение алгоритма Флойда на практике.
1.2 Общие сведения о графах
1.2.1 Графы и способы их представления
1.2.1.1 Основные определения
Граф задается множеством точек или вершин х1, х2, ..., хn и множеством линий или ребер a1, a2, ... , am, соединяющих между собой все или часть точек. Формальное определение графа может быть дано следующим образом [1].
Графом называется двойка вида
G = (X, A),
где X = {xi}, i = 1, 2, ..., n - множество вершин графа, A = {ai}, i = 1, 2,., m - множество ребер графа.
Графы могут быть ориентированными, неориентированными и смешанными (рис.1). Если ребра у множества A ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом или орграфом (рис.1,а).
Рис.1. Примеры ориентированных и неориентированных графов.
Если ребра не имеют ориентации, то граф называется неориентированным (рис.1,б). Граф, в котором присутствуют и ребра, и дуги называется смешанным (рис.1,в). В случае, когда G = (X, A) является орграфом, и мы хотим пренебречь направленностью дуг из множества A, то неориентированный граф, соответствующий G, будет обозначаться и называться неориентированным дубликатом или неориентированным двойником (рис.1,г).
Дуга ai может быть представлена упорядоченной парой вершин (хn, хk), состоящей из начальной хn и конечной хk вершин. Например, для графа G1 (рис.1,а) дуга a1 задается парой вершин (x1, x2), а дуга а3 парой (x2, x3). Если хn, хk - концевые вершины дуги ai, то говорят, что вершины хn и хk инцидентны дуге ai или дуга ai инцидентна вершинам хn и хk.
Дуга, у которой начальная и конечная вершины совпадают, называется петлей. В графе G3 (рис.1,в) дуга a7 является петлей.
Каждая вершина орграфа хi может характеризоваться полустепенью исхода d0(хi) и полустепенью захода dt(хi).
Полустепенью исхода вершины хi -- d0(хi) называется количество дуг, исходящих из этой вершины. Например, для орграфа G1 (рис.1,а) характеристики полустепеней исхода следующие: d0(х1)=1, d0(х2)=2, d0(х3)=2, d0(х4)=1.
Полустепенью захода вершины хi -- dt(хi) называется количество дуг, входящих в эту вершину. Например, для орграфа G1: dt(х1)=2, dt(х2)=1, dt(х3)=2, dt(х4 )=1.
Очевидно, что сумма полустепеней исхода всех вершин графа, а также сумма полустепеней захода всех вершин графа равна общему числу дуг графа, т. е.
где n - число вершин графа, m - число дуг.
Каждая вершина неориентированного графа хi может характеризоваться степенью вершины d(хi).
Степенью вершины хi - d(хi) называется количество ребер, инцидентных этой вершине. Например, для орграфа G1 (рис.1,б) характеристики степеней следующие: d(х1)=2, d(х2)=3, d(х3)=2, d(х4 )=2.
1.2.1.2 Способы описания графов
Теоретико-множественное представление графов
Граф описывается перечислением множества вершин и дуг. Примеры описания приведены для орграфов на рис.2 и рис.3.
G4 = (Х, А),
где Х = {хi}, i = 1, 2, 3, 4 - множество вершин; А = {ai }, i = 1, 2, ..., 6 - множество дуг, причем А = {(х1, х2), (х4, х2), (х2, х4 ), (х2, х3), (х3, х3), (х4 , х1)}.
Рис.2. Пример орграфа.
G5 = (X, A),
где X = {B, C, D, E, F} - множество вершин графа, A = {ai}, i = 1, 2, ..., 5 - множество дуг графа, причем a1 = (F, B), a2 = (B, E), a3 = (F, D), a4 = (E, C), a5 = (C, D).
Рис.3. Пример орграфа.
Задание графов соответствием
Описание графов состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины.
Соответствием Г называется отображение множества Х в Х, а граф в этом случае обозначается парой G = (X, Г).
Отображением вершины хi -- Г(хi) является множество вершин, в которые существуют дуги из вершины хi, т. е. Г(хi) = { хj: дуга (хi, хj)A}.
Так для орграфа на рис.2 описание заданием множества вершин и соответствия выглядит следующим образом:
G4=(X, Г)),
где X = {хi}, I = 1, 2, ..., 4 - множество вершин, Г(х1) = { х2 }, Г(х2) = { х3, х4 }, Г(х3) = {х3}, Г(х4) = { х1, х2 } - отображения.
Для неориентированного или смешанного графов предполагается, что соответствие Г задает такой эквивалентный ориентированный граф, который получается из исходного графа заменой каждого ориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Например, для графа на рис.1,б Г(х2) = { х1, х3, х5 }, Г(х4) ={ х3, х5} и т. д.
Матричное представление графов
Для обработки на ЭВМ графы удобно представлять в виде матриц смежности и инциденций.
Матрица смежности - это квадратная матрица размерностью n x n, (где n - число вершин графа), однозначно представляющая его структуру.
A = {aij}, i, j = 1, 2, ..., n, а каждый элемент матрицы определяется следующим образом:
aij = 1, если дуга (хi, хj),
aij = 0, если нет дуги (хi, хj).
Матрица инциденций представляет собой прямоугольную матрицу размером n x m, где n - количество вершин графа, а m - количество дуг графа. Обозначается матрица инциденций B = = {bij}, i = 1, 2, ..., n, j = 1, 2, ..., m.
Каждый элемент матрицы определяется следующим образом:
bij = 1, если хi является начальной вершиной дуги aj,
bij = -1, если хi является конечной вершиной дуги aj,
bij = 0, если хi не является концевой вершиной дуги aj или если aj является петлей.
Рис.4. Орграф и его матричное представление: а - орграф; б - матрица смежности; в - матрица инциденций
На рис.4, а,б приведен граф и его матрица смежности, по которой можно найти характеристики вершин. Так сумма элементов i-ой строки матрицы дает полустепень исхода вершины хi, а сумма элементов i-го столбца дает полустепень захода вершины хi. По матрице смежности можно найти прямые и обратные отображения. Рассмотрим i-ю строку матрицы. Если элемент aij=1, то элемент графа хj входит в отображение Г(хi). Например, в 2-й строке матрицы А (рис.4,б) единицы стоят в 2-м и 5-м столбцах, следовательно, Г(х2) = { х2, х5}.
Для графа на рис.4,а матрица инциденций приведена на рис.4,в. Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент равный 1 и один - равный - 1, либо все элементы столбца равны 0.
Для неориентированного графа, матрица инциденций определяется так же, за исключением того, что все элементы, равные -1, заменяются на 1.
1.2.2 Пути и циклы в графах
1.2.2.1 Пути и маршруты
Путем в орграфе называется последовательность дуг, в которой конечная вершина всякой дуги, кроме последней, является начальной вершиной следующей дуги.
Например, для графа на рис.5 последовательности дуг
M1: a6, a5, a9, a8, a4 ,
M2: a1, a6, a5, a9, a7 ,
M3: a1, a6, a5, a9, a10, a6, a4
являются путями. Пути могут быть различными.
Рис.5. Пример орграфа
Орцепью (или простым путем) называется такой путь, в котором каждая дуга используется не более одного раза.
Так пути M1 и M2 являются орцепями, а M3 нет, поскольку дуга a6 используется дважды.
Простой орцепью (или элементарным путем) называется путь, в котором каждая вершина используется не более одного раза.
Простой орцепью является путь M2 .
Для неориентированного графа понятия маршрута, цепи и простой цепи аналогичны понятиям пути, орцепи и простой орцепи в орграфе. (В определениях следует заменить слово "дуга" на слово "ребро").
Путь или маршрут можно изображать также последовательностью вершин. Так путь M1 можно представить последователь-ностью вершин х2, х5, х4, х3, х5, х6 , и такое представление часто оказывается более полезным.
1.2.2.2 Вес и длина пути
Иногда дугам графа сопоставляют числа ai сi , называемые весом или длиной, или стоимостью или ценой. В каждом конкретном случае выбирается то слово, которое ближе подходит по смыслу задачи.
Граф G, описываемый тройкой вида
G = (X, A, С)
где Х = { хi }, i =1, 2, 3, ..., n - множество вершин,
А = { ai }, i = 1, 2, 3, ..., m - множество дуг,
С = {Ci}, i = 1, 2, 3, ..., m - множество характеристик дуг, называется графом с взвешенными дугами.
Пример такого графа приведен на рис.6,а. При рассмотрении пути M, представленного последовательностью дуг(a1, a2, ..., aq), за его вес (или длину, или стоимость) принимается число L(M), равное сумме весов всех дуг, входящих в путь, т. е. L(M)=(ci) для всех ai M.
Длиной (или мощностью) пути называется число дуг, входящих в него. Чаще всего термин "длина" употребляется, когда все дуги, входящие в путь, имеют веса, равные 1, т. е. когда вес пути совпадает с его длиной (мощностью).
Рис.6. Взвешенные графы: а - граф со взвешенными дугами; б - граф со взвешенными вершинами; в - взвешенный граф.
Граф с взвешенными вершинами - это граф, описываемый тройкой
G = ( X, А, V ),
где Х = { хi }, i = 1, 2, ..., n - множество вершин графа;
А = { ai }, i = 1, 2, ..., m - множество дуг графа;
V ={ vi }, i = 1, 2, ..., n - множество характеристик вершин.
В качестве характеристик вершин могут выступать "стоимость", "мощность", "вес" и т. п. Пример такого графа приведен на рис.6,б. Для графа со взвешенными вершинами в случае представления пути последовательностью вершин весом пути является сумма весов, входящих в этот путь вершин.
И наконец, взвешенный граф определяется четверкой вида G = (Х, А, V, С), т. е. и дуги, и вершины этого графа имеют некоторые характеристики.
Область применения взвешенных графов в качестве моделей довольно обширна: транспортные задачи, задачи оптимизации сети связи и системы перевозок и др. Одной из известнейших оптимизационных задач является нахождение кратчайших путей в графе со взвешенными дугами.
1.2.2.3 Орциклы и циклы
Особую группу составляют замкнутые пути. Путь a1, a2, ...,aq называется замкнутым, если в нем начальная вершина a1 и конечная вершина aq совпадают. Так, например, для графа на рис.6 можно составить несколько замкнутых путей:
М1: a3, a6, a11,
М2: a11, a3, a4, a7, a1, a12, a9 ,
М3: a3, a4, a7, a10, a9, a11.
Пути М1 и М3 являются замкнутыми простыми орцепями, называемыми контурами или простыми орциклами, поскольку в них одна и та же вершина используется только один раз (за исключением начальной и конечной). Путь М2 не является контуром, так как вершина х1 используется в нем дважды. Контур, проходящий через все вершины графа, имеет особое название гамильтонов контур. Путь М3 является гамильтоновым контуром. Он показан штриховой линией на рис.7.
Рис.7. Орциклы в графе
Для неориентированного графа замкнутым маршрутом является неориентированный двойник замкнутого пути, т. е. замкнутым маршрутом является маршрут, в котором совпадают начальные и конечные вершины.
Для неориентированного графа понятия цикла и гамильтонова цикла аналогичны понятиям орцикла и гамильтонова контура в орграфе.
Эйлеровым циклом в графе называется цикл, содержащий все ребра графа. Граф, содержащий эйлеров цикл, называется эйлеровым графом.
Основная теорема о существовании эйлерова цикла формулируется так: связный неориентированный граф G содержит эйлеров цикл тогда и только тогда, когда число вершин нечетной степени равно нулю (0 или 2).
Эйлер первым в своей знаменитой задаче о Кенигсбергских мостах поставил вопрос о существование такого цикла.
На реке Преголя в Кенигсберге было два острова. Они соединялись между собой и с берегами реки семью мостами, как схематично показано на рис.8. Задача заключалась в том, чтобы за одну прогулку обойти все семь мостов, проходя по каждому мосту только один раз, и вернуться в исходное место.
Если каждый берег реки и острова считать вершинами графа, а каждый мост - ребром, то карту рис.8,а можно представить в виде графа на рис.8,б и ответ на поставленный вопрос зависит теперь от существования эйлерова цикла в этом графе. Эйлер установил, что указанный граф не содержит эйлерова цикла, и этот результат ознаменовал рождение теории графов.
Рис. 8. а - схема Кенигсбергских мостов; б - эквивалентный граф
1.3 Алгоритм Флойда
Предположим, что мы имеем помеченный орграф, который содержит время полета по маршрутам, связывающим определенные города, и мы хотим построить таблицу, где приводилось бы минимальное время перелета из одного (произвольного) города в любой другой. В этом случае мы сталкиваемся с общей задачей нахождения кратчайших путей, то есть нахождения кратчайших путей между всеми парами вершин орграфа [2].
Формулировка задачи. Есть ориентированный граф G(V, E), каждой дуге (ребру) (v, w) этого графа сопоставлен неотрицательный вес Cvw. Общая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин v, w любого пути от вершины v в вершину w, длина которого минимальна среди всех возможных путей от v к w.
Для решения задачи воспользуемся методом Флойда. Пусть все вершины орграфа последовательно пронумерованы от 1 до n. Алгоритм Флойда использует матрицу A(n*n), в которой находятся длины кратчайших путей:
Aij=Cij, если i?j;
Aij=0, если i=j;
Aij=? если отсутствует путь из вершины i в вершину j.
Над матрицей A выполняется n итераций. После k-ой итерации Aij содержит значение наименьшей длины пути из вершины i в вершинуj, причем путь не проходит через вершины с номерами большими k.
Вычисление на k-ой итерации выполняется по формуле:
Верхний индекс k обозначает значение матрицы A после k-ой итерации.
Для вычисления проводится сравнение величины (то есть стоимость пути от вершины i к вершине j без участия вершины k или другой вершины с более высоким номером) с величиной (стоимость пути от вершины i к вершине k плюс стоимость пути от вершины k до вершины j). Если путь через вершину k дешевле, чем , то величина изменяется.
2. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
2.1 Особенности программной реализации
Алгоритм реализовывается на языке Java в среде Oracle JDeveloper с использованием сервлетов и JSP страниц. На JSP странице Intro.jsp можно выбрать тип загрузки данных. Класс MainServletClass обрабатывает ответ пользователя на вопрос, каким способом будут загружаться данные и выводит соответствующие html-страницы. Если загрузка выполняется вручную, то вызывается метод класса FormToFill, который представляет страницу с матрицей весов. После ее заполнения, а также после указания пути до файла вызывается метод service класса PrepareInfo. Здесь реализуется алгоритм, результат готовится и выводится на экран.
В программе возможны два способа задания входных данных: вручную и из файла. В первом случае предлагается заполнить таблицу весов графа, во втором - указать файл с данными. В файле значения весов должны разделяться пробелами, переход на новую строку трактуется как переход на новую строку в таблице.
Пример формата файла с данными:
0 10 0 30 90
0 0 50 0 0
0 0 0 0 15
0 0 20 0 60
0 0 0 0 0
В обоих случаях входные данные представляют собой числовую положительную матрицу, на диагонали которой стоят нули, т.е. рассматриваются орграфы без петель. В программе задано ограничение на количество вершин - их должно быть не более 30.
Ответ представлен в виде таблицы, размеры которой соответствуют количеству вершин в графе. В каждой ячейке указан порядок следования вершин в оптимальном пути, а также сумма весов дуг, входящих в него.
2.2 Реализация алгоритма
2.2.1 Входные данные
Задается матрица весов дуг elem_weight[][], в которой указаны веса дуг между вершинами i и j. Матрица симметричная и положительная. Если i и j не связаны дугой, то elem_weight[i][j]=10000.
2.2.2 Выполнение программы
Выполнение программы можно разделить на пункты:
1. Заполнение массива elem_weight[][] значениями весов.
2. Вызов метода GetPath, в котором непосредственно вычисляются кратчайшие пути в графе. Метод возвращает массив paths[][], в котором хранятся полученные пути. Если пути между двумя вершинами не существует, в элементе массива хранится значение «-». Алгоритм метода GetPath показан ниже.
3. Для более удобного просмотра результата из каждого элемента полученного массива извлекаются номера вершин и помещаются в массив path_tops[] (массив заново инициализируется для каждого пути). После несложных преобразований на экран выводятся пути в виде списков вершин. Также по полученным номерам вершин, с использованием данных из массива elem_weight[][], определяется сумма весов вершин и тоже выводится на экран.
2.2.3 Алгоритм метода GetPath
Для удобства непосредственно алгоритм Флойда вынесен в отдельный метод GetPath. В качестве входного параметра метод получает массив весов матрицы elem_weight[][] и возвращает массив paths[][], содержащий кратчайшие пути между вершинами. Пути представлены в виде последовательностей номеров вершин, где крайние являются номерами начальной и конечной вершин. Вершины разделены «=>».
В получаемом массиве элементы elem_weight[i][j]равны весам дуг, исходящих из i-ой вершины в j-ую, либо, в случае, если такой дуги не существует, нулю. Для реализации метода Флойда всем нулевым элементам приравнивается значение, характеризующее . В написанной программе это число 10 000. Алгоритм преобразования массива представлен на рис.9.
Рис.9. Алгоритм повторной инициализации массива весов
Преобразовав массив весов, можно реализовать алгоритм Флойда. В процессе его выполнения производится заполнение массива кратчайших путей в графе. Алгоритм представлен на рис.10.
Рис.10. Алгоритм Флойда.
3. ПРИМЕР ИСПОЛЬЗОВАНИЯ ПРОГРАММНОЙ РЕАЛИЗАЦИИ
В качестве примера работы программы ниже рассмотрен граф, в котором необходимо найти все кратчайшие пути.
Матрица весов графа:
0 10 0 30 90
0 0 50 0 0
0 0 0 0 15
0 0 20 0 60
0 0 0 0 0
В начале пользователю предлагается выбрать способ загрузки данных (рис.11).
Рис.11. Выбор способа загрузки данных
Если было выбрано чтение информации из файла, выбрать его можно на следующей странице (рис.12). Кроме того, на каждой странице можно вернуться к главной.
Рис.12. Выбор файла с данными
Если файл не введен или данные в указанном файле записаны не корректно, то следующая страница будет содержать сообщение об этом, а также предложение ввести данные заново. Пример такой страницы, в случае неверных данных в файле, представлен на рис.13.
Рис.13. Сообщение об ошибке при чтении данных из файла
Если было выбрано введение данных вручную, то следующим шагом будет введение количества вершин в графе (рис.14). Это значение ограничено 30. Если значение не ведено или введено не верно, то выведется сообщение об ошибке с предложением повторить операцию заново.
Рис.14. Введение количества вершин
После указания количества вершин требуется заполнить матрицу весов графа. Веса представляют собой положительные числа, кроме того, на диагонали могут стоять только нули.
Рис.15. Заполнение матрицы весов
Если данные введены неверно, то на странице печатается сообщение об этом с описанием ошибки и предложением ввести данные заново. Пример такого сообщения показан на рис.16.
Рис.16. Сообщение об ошибке
Если данные, введенные вручную или считанные из файла, корректны, то выводится результат (рис.17). Он представляет собой матрицу, в ячейках которой указаны вершины, входящие в путь, последовательность их обхода и суммарный вес дуг, которые входят в указанный путь. Если путь из одной вершины в другую отсутствует, в ячейке ставится знак «-».
Рис.17. Вывод матрицы кратчайших путей.
ЗАКЛЮЧЕНИЕ
граф алгоритм флойд кратчайший поиск
В данной курсовой работе была изучена тема «Поиск кратчайшего пути в графе» на основе алгоритма Флойда. В соответствии с требованием курсовой работы была разработана программа реализации данного алгоритма. Программа написана в среде Oracle JDeveloper на языке Java с использование сервлетов и JSP страниц. Возможны два варианта ввода данных: вручную и из файла.
Работоспособность данной программы была проверена на тестовых примерах, один из которых представлен в объяснительной записке.
Размещено на Allbest.ru
Подобные документы
Разработка алгоритма реализации на ЭВМ процесса поиска кратчайшего пути в графе методом Дейкстры. Программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа. Проверка работоспособности программы на тестовых примерах.
реферат [929,8 K], добавлен 23.09.2013Блок-схема алгоритма Флойда. Разработка его псевдокода в программе Microsoft Visual Studio. Программа реализации алгоритмов Беллмана-Форда. Анализ трудоемкости роста функции. Протокол тестирования правильности работы программы по алгоритму Флойда.
курсовая работа [653,5 K], добавлен 18.02.2013Изучение основных понятий и определений теории графов. Рассмотрение методов нахождения кратчайших путей между фиксированными вершинами. Представление математического и программного обоснования алгоритма Флойда. Приведение примеров применения программы.
контрольная работа [1,4 M], добавлен 04.07.2011Алгоритмы, использующие решение дополнительных подзадач. Основные определения теории графов. Поиск пути между парой вершин невзвешенного графа. Пути минимальной длины во взвешенном графе. Понятие кратчайшего пути для графов с помощью алгоритма Флойда.
реферат [39,6 K], добавлен 06.03.2010Алгоритм сортировки Шейкер: математическое описание задачи и описание алгоритма. Алгоритм покрытия: построение одного кратчайшего покрытия. Описание схемы и работы алгоритма на графах: нахождение кратчайшего пути. Контрольные примеры работы алгоритмов.
курсовая работа [43,8 K], добавлен 19.10.2010Области применения теории графов. Алгоритм решения задачи поиска инвариантного и полного графа. Реализация программы с графическим интерфейсом пользователя на основе алгоритма. Реализация редактора графа и вывод полученных результатов в понятной форме.
курсовая работа [493,3 K], добавлен 27.12.2008Графы: определения, примеры, способы изображения. Смежные вершины и рёбра. Путь в ориентированном и взвешенном графе. Матрица смежности и иерархический список. Алгоритм Дейкстры - алгоритм поиска кратчайших путей в графе. Работа в программе "ProGraph".
презентация [383,8 K], добавлен 27.03.2011Теоретическое исследование вопроса и практическое применение. Общие сведения о графах. Алгоритм Дейкстры. Особенности работы в среде. Программная реализация. Описание алгоритма и структуры программы. Описание программных средств. Текст программы.
курсовая работа [1,0 M], добавлен 27.11.2007Корректность определения кратчайших путей в графе и рёбра отрицательной длины. Анализ алгоритмов Дейкстры, Беллмана-Форда, Флойда-Уоршелла. Вычисление кратчайших расстояний между всеми парами вершин графа. Топологическая сортировка ориентированного графа.
презентация [449,3 K], добавлен 19.10.2014Понятие алгоритма как набора инструкций, описывающего порядок действий. Поиск в ширину - метод обхода графа и поиска пути в нем. Пример работы алгоритма поиска в ширину, его неформальное и формальное описание. Реализация с помощью структуры "очередь".
курсовая работа [684,8 K], добавлен 05.04.2015
