Программная реализация алгоритма Дейкстры

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ХАРКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ

 

 

Кафедра информатики

 

 

 

КУРСОВАЯ РАБОТА

Тема: “Программная реализация алгоритма Дейкстры ”

по дисциплине «Программирование»

 

 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

 

 

 

 

 

 

 

Выполнил: Руководители:

cтудента группы КИ-11-6 Руденко Д. А.

Партас А.О. 

 

 

 

Харьков 2013

СОДЕРЖАНИЕ

 

Введение………………………………………………....……
1 Постановка задачи и сфера  её применения…..………......
2 Теоретическая часть…………………………………….....
2.1 Формальное определение алгоритма ………………...
2.2 Рассмотрение алгоритма Дейкстры на примере ….
3 Программная реализация…………………………….…….
3.1 Описание алгоритма и структуры программы……..
3.2 Описание программных средств…………………….
4 Инструкция пользователя………………………………….
Вывод….………………………………………………….….
Перечень ссылок……………………………………………...
Приложение А Текст программы………………………..
Приложение Б Окно консоли..………………………….…..

ВВЕДЕНИЕ

 

Навигация движения путника от пункта A в пункт B всегда была интересной проблемой, которой интересовались программисты игр.

Есть различные способы реализации таких алгоритмов.

Волновой алгоритм

Прекрасно подойдет, если все пути из вершины в соседнюю равны по длине (цене, весу) Время O(n).

Алгоритм Форда-Беллмана

Найти наименьшие стоимости проезда из 1-го города во все остальные за время O(n3) без ограничений на веса.

Алгоритм Флойда

Найти наименьшие стоимости проезда из всех городов во все за время O(n3) без ограничений на веса.

Алгоритм Дейкстры

Найти наименьшие стоимости проезда из 1-го города во все остальные за время O(n2) при положительных ценах.

Наиболее эффективный алгоритм решения задачи о кратчайшем пути первоначально дал Дейкстра. В общем случае этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от некоторой вершины s к рассматриваемой вершине. Эти пометки постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации только одна из временных пометок становится постоянной. Последнее указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от t к рассматриваемой вершине.

В данном курсовом проекте реализуется алгоритм Дейкстры.

1 ПОСТАНОВКА ЗАДАЧИ И СФЕРА ЕЁ ПРИМЕНЕНИЯ

 

Целью данного курсового проекта является программная реализация алгоритма Дейкстры (алгоритм поиска кратчайшего пути между двумя любыми вершинами графа).

Программа должна работать следующим образом:

– пользователь вводит количество вершин и длины рёбер графа,

– после выполнения программы на экран должны выводиться кратчайший путь между двумя заданными вершинами и его длина.

Программа должна быть реализована на объектно-ориентированном языке С++.

2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

 

 

2.1 Формальное определение алгоритма

 

Дан простой взвешенный граф G(V,E) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.

 

Рис. 2.1 – Простой взвешенный граф G(V,E)

 

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается.  
В противном случае из еще не посещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.

 

2.2 Рассмотрение алгоритма Дейкстры на примере

 

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке 2.2. Пусть требуется найти расстояния от 1-й вершины до всех остальных.

Рис. 2.2 – Исходный граф

 

Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» – длина пути. Рядом с каждой вершиной обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.

 

 

Рис. 2.3 – Присвоение меток всем вершинам

 

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Ее соседями являются вершины 2, 3 и 6.

Рис. 2.4 – Первый шаг

 

Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до нее минимальна. Длина пути в нее через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7. На графике изначально рассмотрена вершина 3.

Рис. 2.5 – Присвоение 3-й вершине новой метки

 

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й.

 

 

Рис. 2.6 – Рассмотрение остальных вершин

 

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

 

Рис. 2.7 – Первая вершина рассмотрена

 

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.

Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 — вершина 4/*3*/. Если идти в неё через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22< , устанавливаем метку вершины 4 равной 22.

 

 

Рис. 2.8 – Рассмотрение 2-й вершины

 

Ещё один сосед вершины 2 — вершина 3. Если идти в неё через 2, то длина такого пути будет = 7 + 10 = 17. Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем ее как посещенную.

 

 

Рис. 2.9 – Результат рассмотрения 2-й вершины

 

Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После ее «обработки» получим такие результаты:

 

 

Рис. 2.10 – Третий шаг

 

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).

 

 

Рис. 2.11 – Дальнейшие шаги

 

Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на рисунке2.11: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

 

 

3 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

 

 

3.1 Описание алгоритма и структуры программы

 

Данная программа разработана для нахождения минимального пути между двумя вершинами в графе. Также она находит длину этого пути.

При запуске программы на экран выводится запрос на ввод количества вершин. После, вводятся веса путей между вершинами и выводится матрица  путей. После рёбрам, равным нулю присваивается значение 65535.

Следующим этапом выполнения программы является запрос о вводе номеров вершин, между которыми необходимо узнать путь. В случае, если начальная и конечная вершины совпадают, программа завершает работу и выдает соответствующее сообщение. В противном случае выполняется  алгоритм Дейкстры.

Результатом программы является вывод кратчайшего пути на экран (и в файл) между заданными вершинами, а также вывод длины этого маршрута. Если пути между заданными вершинами не существует – выводится соответствующее сообщение.

Ниже на рисунке 4.1 приведен общий алгоритм работы программы, а на рисунке 4.2 алгоритм Дейкстры.

 

Рис. 3.1 – Общий алгоритм программы

 

Рис. 3.2 – Алгоритм Дейкстры

3.2 Описание использованных программных средств

 

Таблица 3.1 – Описание переменных

 

Переменная	Тип	Описание
n	int	Количество вершин грифа
i,j	int	Счётчики
p	int	Номер кратчайшего пути и наименьшей длины пути
xn	int	Номер начальной вершины
xk	int	Номер конечной вершины
flag[n]	int	Массив, i-й элемент которого имеет значение 0, когда i-й путь и расстояние временные, и принимает значение 1, когда i-й путь и расстояние становятся  постоянными
vertex[n][n]	int	Массив i-j элемент которого содержит расстояние между i-й и j-й точками (вершинами)
buf[30]	char	Строчная переменная, которая содержит промежуточные значения пути
path[30][30]	char	Массив строк, который содержит пути.
len[n]	int	Массив, который содержит длины путей (path)

 

 

 

 

 

4 ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ

 

При запуске программы выводится окно со следующими запросами:

1. Ввод количества вершин.
2. Ввод веса рёбер. В программе расстояния от хi до xi+1 и xi+1 до хi считаются равными. Если ребра между указанными вершинами не существует, введите ноль.

На экран выводится матрица путей.

3. Ввод номер вершины начальной точки.
4. Ввод номер вершины конца пути.

После выполнения программы на экран (и в файл) выводится кратчайший путь между заданными вершинами и его длина.

ВЫВОД

 

В данном курсовом проекте была разработана программа, реализующая алгоритм Дейкстры. Программа была написана на Microsoft Visual C++ 2008.

Также были углублены знания, полученные в процессе  выполнения лабораторных работ по предмету «Программирование».

Исходными данными для работы программы являются значения, введенные с клавиатуры (числа). При введении неверного значения (буквы) выводится сообщение об ошибке ввода.

В качестве выходной информации выводится кратчайший путь между заданными вершинами графа, а также файл, содержащий туже информацию.

Для хранения данных используется текстовый файл.

ПЕРЕЧЕНЬ ССЫЛОК

 

1. Таха  Хэмди А. Введение в исследование операций, 7-е издание.: М.: Издательский дом «Вильямс»,  2007. –912 с.
2. Конспект лекций.

Приложение А

Текст программы

//Copyright FIOS inc. 2003 - 2009

#include "stdafx.h"

#include <iostream>

#include <fstream>

#include <string.h>

#include <conio.h>

 

using namespace std;

 

char s[80], path[80][11];

//=================================================================

bool scan_matr (int **vertex, int n)

{

int i, j;

  for(i = 0; i < n; i++)

for(j = i + 1; j < n; j++)

{

    cout << "enter lenth behind x" << i + 1 << " and x" << j + 1 << ": ";

    cin  >> vertex[i][j];

 if ((vertex[i][j] > 65536) || (vertex[i][j] < 0))

{

cout << "Vrong input" << endl;

_getch ();

 return 0;

}

cout << endl;

}

return 1;

}

//================================================================

void null_matr (int **vertex, int n)

{

int i, j;

 

for(i = 0;  i < n; i++)

 for(j = 0; j < n; j++)

  if(vertex[i][j] == 0)

   vertex[i][j] = 65535;

}

//================================================================

void print_matr (int **vertex, int n)

{

int i, j;

for (i = 0; i < n; i++)

{

for (j = 0; j < n; j++)

cout << vertex[j][i] << "   ";

    cout << endl << endl;