Теория о нахождении кратчайших путей

ВВЕДЕНИЕ

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.
Нахождение кратчайшего пути – жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от города до города), в системах автопилота, для нахожденияоптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п.
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.
Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:
• алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);
• алгоритм Флойда (для нахожденияоптимального маршрута между всеми парами вершин);
• алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами).
Указанные алгоритмы легко выполняются при малом количестве вершин в графе. При увеличении их количества задача поиска кратчайшего пути усложняется. Здесь на помощь приходит современная техника.
Компьютерные средства и информационные технологии повысили возможноститакого всеохватывающего метода изучения и создания, как моделирования объектов, явлений и процессов – как тех, что существуют в природе, так и тех, что создаются человеком искусственно.

1 ПОСТАНОВКА ЗАДАЧИ И СФЕРА ЕЁ ПРИМЕНЕНИЯ
Основной задачей данного курсового проекта является программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа.Программа должна работать так, чтобы пользователь вводил количество вершин и длины рёбер графа, а после обработки этих данных на экран выводился кратчайший путь между двумя заданными вершинами и его длина. Необходимо предусмотреть различные исходы поиска, чтобы программа не выдавала ошибок и работала правильно.
Данная программа может использоваться в дискретной математике для исследования графовили в качестве наглядного пособия, демонстрирующего применение алгоритма Дейкстры на практике.

2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
2.1 Сведения о графах
Граф G (рис.2.1.1) задается множеством точек (вершин) х1, х2,..., хn. (которое обозначается через Х) и множеством линий (ребер) а1, а2,...,аm. (которое обозначается символом А), соединяющих между собой все или часть этих точек. Такимобразом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом.
[pic]

Например, если дорога имеет не двух-, а одностороннее движение то направление этого движения будет показано стрелкой.
Если ребра не имеюториентации, то граф называется неориентированным, (двухстороннее движение).
В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин, ее направление предполагается заданным от первой вершины ко второй.
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличнойот последней, является начальной вершиной следующей.
Так, на рис. 2.1.2 путями являются последовательности дуг:
а6, а5, а9, а8, а4. (1)
а1, а6, а5, а9. (2)
а1, а6, а5, а9, а10, а6, а4. (3)
Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не большеодного раза.
Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2).
Маршрут есть неориентированный “двойник” пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе.
Иногда дугам графа приписываются числа, называемые весом, стоимостью,...