Кратчайшие пути. Алгоритмы их нахождения - Курсовая работа

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается. Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п. Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом. Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути: алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами); Цель: с помощью программы Microsoft Visual Basic Express Edition разработать приложение, позволяющее искать кратчайшие пути в произвольном графе.Граф G задается множеством точек или вершин x1, х2,,……, xn (которое обозначается через X) и множеством линий или ребер a1, а2……, an (которое обозначается символом А), соединяющих между собой все или часть этих точек. Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом (рис.1.1 (а)). Если ребра не имеют ориентации, то граф называется неориентированным (рис.1.1 (6)). Далее, когда дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т.е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. В случае неориентированного графа или графа, содержащего и дуги, и неориентированные ребра (см., например, графы, изображенные на рис.1.1 (6) и 1.1 (в)), предполагается, что соответствие Г задает такой эквивалентный, ориентированный граф, который получается из исходного графа заменой каждого неориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины.Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Дуги, имеющие общие концевые вершины, называются смежными. Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза.Выбор алгоритма нахождения кратчайшего пути зависит от вида графа в котором требуется найти кратчайший путь.Волновой алгоритм - алгоритм, позволяющий найти минимальный путь в графе с ребрами единичной длины. На двумерной клетчатой карте (матрице), состоящей из "проходимых" и "непроходимых" клеток, обозначена клетка старта и клетка финиша. От старта во все направления распространяется волна, причем каждая пройденная волной клетка помечается как "пройденная". Если волна прошла все доступные клетки, но так и не достигла клетку финиша, значит, путь от старта до финиша проложить невозможно. На втором этапе, начиная с ячейки В, по определенным правилам, выполняется переход от ячейки k-ого фронта к ячейке k-1 фронта до ячейки А.Алгоритм Дейкстры (Dijkstra’s algorithm) - алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных (если таковые имеются). Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. алгоритм маршрут оптимальный вершина Причем вершина, помеченная последней (на данный момент) расположена ближе к исходной вершине, чем все непомеченные, но дальше, чем все помеченные. Сначала помечается исходная вершина; следующей, очевидно, будет помечена вершина, ближайшая к исходной, и смежная с ней.Алгоритм Беллмана - Форда применяется для нахождения кратчайшего расстояния от вершины [s] до остальных вершин. Алгоритм может обнаруживать побочное явление таких графов - циклы отрицательной величины по которым можно вечно крутиться, уменьшая расстояние до вершин.Процедура находит пути минимального веса в графе G= (V,E) заданном весовой матрицей W у которой элемент W [i, j] равен весу ребра соединяющего i-ую и j-ую вершины. Путь ищется для всех пар вершин графа. Следует заметить, что если в графе существует контур отрицательной сумарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, "прокрутившись" в контуре необходимое количество раз. Останавливаясь подробнее надо заметить, что если граф неориентированный (W [i,j] - симметрична), то ребро с отрицательным весом является как раз таким контуром (туда-сюда можно бегать пока не сделаем вес достаточно малым)Алгоритм предназначен для нахождения К путей минимальной длины во взвешенном графе соединяющих вершины u1,u2. Ищутся пути, которые не содержат петель. Второй путь ищем перебирая кратчайшие отклонения от первого, третий кратчайшие отклонения от второго и т.д. Проверить, совпадает ли подпуть, образованный

Содержание

Введение

Глава 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) Разработка программы поиска кратчайших путей

Актуальность данной работы заключается в том, что часто бывает полезно и наглядно изображать некоторую ситуацию в виде графов. Графы встречаются во многих областях под разными названиями: "структуры" в гражданском строительстве, "сети" в электротехнике, "социограммы" в социологии и экономике, "молекулярные структуры" в химии, "дорожные карты", электрические или газовые "распределительные сети" и так далее. И по этому крайне важно уметь находить кратчайшие пути в графе.