Составление кратчайших маршрутов

Для графа, изображенного рис.14, найдем кратчайшие пути от вершины до всех остальных вершин графа, используя алгоритм Дейкстры, реализацию алгоритма представим в виде таблицы (см. табл.2).Таблица 2Алгоритм Дейкстры поиска кратчайших путей в графе от вершины Шаг №12345678Каждая вершина получила окончательную метку (в табл.2окончательные метки обозначены символом «звездочка»), следовательно, алгоритм закончил свою работу, и мы определили длины всех кратчайших путей из заданной вершины до остальных вершин графа. Возникает вопрос, возможно ли по имеющейся таблице, восстановить сами кратчайшие пути?Ответ на этот вопрос можно дать положительный, рассмотрим, например, как по табл.1 найти кратчайший путь от вершины до вершины .Процесс восстановления пути производим «с конца». Имеем, вершина получила окончательную метку на шаге № 6, просматривая таблицу, ищем шаг, на котором метка указанной вершины была другой, отличной от окончательной метки – шаг № 5, на пятом шаге окончательная метка была у вершины , следовательно, дуга , входит в кратчайший путь. Метка вершины отличалась от окончательной метки на шаге № 3, на третьем шаге окончательная метка была у вершины , следовательно, дуга , входит в кратчайший путь. Повторяем подобные рассуждения, пока не доберемся до начальной вершины , искомый путь.Аналогично можно восстановить и пути до остальных вершин графа.Стоит сказать пару слов относительно эффективности метода Дейкстры, последняя существенно зависит от того, как организован поиск вершины с наименьшим текущим расстоянием. В настоящее время достаточно эффективным считается метод, который связывают с именем А. Б. Грибова [2](некоторые полезные ссылки и обзоры возможного дальнейшего развития данной проблематики можно найти также в[9]).2.2.2. Алгоритм Форда – БеллманаОдним из ограничений в рассмотренном ранее алгоритме Дейкстры являлось ограничение по весам дуг графа, а именно, под запретом были отрицательные веса дуг. Существует алгоритм поиска кратчайшего пути от заданной вершины орграфа до всех остальных вершин графа, работающий в более общем случае, когда предполагается лишь отсутствие в данном графе контуров с отрицательной длиной. С этим алгоритмом обычно связывают имена Л.Р. Фордаи Р.Е. Беллмана[5, с. 115].В рамках данной работы мы не будем подробно останавливаться на рассмотрении указанного алгоритма. Формальное описание алгоритма и пример его применения к конкретному графу даны в приложениях к работе (см. стр. 111).ЗАКЛЮЧЕНИЕКак показывает практика можно привести многочисленные примеры ситуаций из различных сфер жизни, попадающие в разряд прикладных задач, эффективно решаемых средствами теоретико-графового аппарата. Широтаобласти возникновения подобных примеров обуславливает актуальность выбранной для исследования темы.Целью данной курсовой работы являлось исследование алгоритмов математического аппарата теории графов, а также их применения, при решении задачи о кратчайших путях в графе. В связи с чем, в процессе работы над темой, были решены следующие задачи: рассмотрены основные понятия теории графов;введена классификация видов графов;исследованы базовые положения,связанные с понятием «маршрута» в графе;проанализированы существующие алгоритмы поиска кратчайших путей в графе;разобраны практические примеры применения алгоритмов поиска кратчайших путей в графе.Итак, можно сделать вывод, что теория графов – это математическая теория, приложимая как к наукам о поведении (теории информации, кибернетике, играм, транспортным сетям), так и к теории множеств, теории матриц и другим, чисто абстрактным дисциплинам.Методы теории графов разрабатываются применительно к различным ситуациям, всевозможных научных отраслей, как то: экономика, химия, биология и многие другие. Стоит отметить, что классификация видов графов довольно разнообразна и включает в себя такие отличительные особенности графов как то: наличие или отсутствие в графе петель, кратных ребер (дуг), ориентированность ребер графа, связность и некоторые другие. Основное внимание в работе сосредоточено на задаче поиска кратчайших путей в графе. То есть на задачах такого рода, когда формализации самой задачи предшествовала конкретная (прикладная) проблема.С целью более детального исследования основных положений рассмотренной в курсовой работе оптимизационной задачи выделено несколько основополагающих критериев, согласно которым подобраны методы решения. Рассмотрены некоторые типовые алгоритмы решения поставленной задачи (алгоритмы Флойда – Уоршелла, Дейкстры и Форда – Беллмана), а также приведены примеры применения данных алгоритмов к решению конкретных практических задач.Однако стоит отметить, что в работе затронуты лишь базовые понятия теории, и она носит ознакомительный характер. Для более углубленного изучения темы можно обратиться к перечню литературы, использованной при написании курсовой работы.СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ИНТЕРНЕТ-РЕСУРСОВАндерсон Дж. А. Дискретная математика и комбинаторика. – М.: Изд. дом «Вильямс», 2004. – 960 с.Аникеич А.А., Грибов А.Б., Сурин С.С. Сменно-суточное планирование работы грузовых автомобилей на ЭВМ. – М.: Транспорт, 1976. – 152 с.Берж К. Теория графов и ее применения. – М.: Изд. иностр. лит., 1962. – 319 с.Иванов Б.Н. Дискретная математика. Алгоритмы и программы: учеб.пособие. – М.: Лаборатория базовых знаний, 2003. – 288 с.Липский В. Комбинаторика для программистов. – М.: Мир, 1988. – 213 с.Майника Э. Алгоритмы оптимизации на сетях и графах. – М.: Мир, 1981. – 324 с.Новиков Ф.А. Дискретная математика для программистов: учебник. – СПб.: Питер, 2000. – 304 с.Оре О. Теория графов. – 2-е изд. – М.: Наука, Главная редакция физико-математической литературы, 1980. – 336 с.Романовский И.В. Дискретный анализ: учеб. пособие. –2-е изд. – СПб.: Невский диалект, 2000. – 240 с.Татт У. Теория графов: монография. – М.: Мир, 1988. – 424 с.ТахаХемди А. Введение в исследование операций. – 7-е изд. – М.: Изд. дом «Вильямс», 2005. – 912 с.Харари Ф. Теория графов. – М.: Мир, 1973. – 301 с.Ху Т. Целочисленное программирование и потоки в сетях. – М.: Мир, 1974. – 520 с.ПРИЛОЖЕНИЕ №1Формальное описание алгоритма Форда – БеллманаДано: Орграф с вершинами, выделенной вершиной , матрицей весов дуг , (граф не содержит контуров отрицательной длины).Результат: Расстояния от вершины до всех вершин графа (см. [5, с. 112]).Алгоритм:1. begin2. for do ; ;3. for to do 4. for do5. for do 6. endДоказательство правильности алгоритма приведено в [5, с. 115].ПРИЛОЖЕНИЕ №2Пример применения алгоритма Форда – БеллманаПроиллюстрируем на примере работу алгоритма. Пусть дан граф, см. рис. 1:Для данного графа составим следующую матрицу весов дуг (отсутствие петель и/или дуг в графе отображается в матрице символом ).Результат работы алгоритма сведем в табл. 1:Таблица 1Работа алгоритма Форда-Беллмана013101442014330143