Графы. Поиск кратчайшего пути из заданной вершины в заданную

Размещено на http://www.allbest.ru/

МИНОБРНАУКИ РОССИИ

Федеральное государственное автономное образовательное учреждение высшего образования

«Санкт-Петербургский политехнический университет Петра Великого»

Институт компьютерных наук и технологий

Высшая школа программной инженерии

Курсовая работа по дисциплине: «Алгоритмы и структуры данных»

Тема: «Графы. Поиск кратчайшего пути из заданной вершины в заданную»

Выполнил

студент гр.13537/1 Е. В. Лукаш

Руководитель

Ст. преподаватель Т.Н. Самочадина

Санкт-Петербург 2017



Содержание

Введение

1. Детальная постановка задачи

2. Обоснование способа представления данных

3. Структура проекта

4. Особенности реализации методов

5. Отладка и тестирование

Заключение

Список использованной литературы

Приложения



Введение

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

Если каждому ребру соответствует какое-либо число - вес, то граф называется взвешенным.

Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.

Если ребра не имеют ориентации, граф называется неориентированным.

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

Граф называется пустым, если в нем нет ребер. Полным - если в нем каждые две вершины смежные.

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



1. Детальная постановка задачи

Условие поставленной передо мной задачи выглядит следующим образом:

Дан неориентированный граф с количеством вершин size и инициализированным весов ребер. Необходимо определить кратчайший путь из заданной вершины в заданную через вершины графа. И вывести на экран суммарный вес ребер, через которые проходит этот путь.

Пример выполнения задания:

0	7	9	0	0	14
7	0	10	15	0	0
9	10	0	11	0	2
0	15	11	0	6	0
0	0	0	6	0	9
14	0	2	0	9	0

Необходимо найти кратчайший путь из 1 в 5.

1) Метка вершины 1 полагается равной 0, метки остальных вершин - недостижимое большое число.

2) Первый шаг:

Обходим соседей вершины 1 по очереди.

Для вершины 2: длина пути в нее через вершину 1 равна сумме метки вершины 1 и длины ребра, соединяющих вершины 1 и 2

Получаем: 0+7=7

Так как 7 < ? , то меняем метку вершины 2 на 7.

Аналогично находим метки для вершин 3 и 6:

для 3: 0+9=9

для 6: 0+14=14

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным изменению не подлежит. Вершина 1 отмечается как посещенная.

3) Второй шаг:

Обходим соседей вершины 2. (так как метка у вершины 2 меньше всех остальных)

для 3: 7+10 =17 (так как 9<17, то метка не меняется)

для 4: 7+15=22

4) Третий шаг:

Обходим соседей вершины 3:

5) Четвертый шаг:

Обходим соседей вершины 6:

для 5: 11+9=20

6) Пятый шаг:

Конечный ответ: 20

2. Обоснование способа представления данных

Для представления графа я использовала двумерный массив типа int с выделяемой динамической памятью. Размер массива - количество вершин в графе. Элементы массива - вес ребер, соединяющих две вершины. Если вершины не соединены, то вес ребра равен нулю.

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

Для хранения информации о «статусе» вершин (проверена или нет) в ходе работы алгоритма я создала одномерный массив типа bool с выделяемой динамической памятью. Размер массива - количество вершин в графе.

3. Структура проекта

Мой проект содержит в себе один файл «graph.cpp», в котором обозначены все используемые структуры данных, инициализирован двумерный массив смежности графа и прописан алгоритм поиска кратчайшего пути из заданной вершины в заданную.

4. Особенности реализации методов

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

Алгоритм представляет собой повторяющийся ряд шагов для каждой проверяемой вершины. Для обозначения кратчайшего пути из одной вершины в другую используются метки, присвоенные каждой отдельной вершине. Метка представляет собой сумму всех ребер с минимальным весом, соединяющих одну вершину с другой. У каждой вершины может быть только одна метка. Результатом работы алгоритма будет метка, присвоенная «конечной» вершине.

В программе присутствует ряд проверок на корректность введенных данных:

· размером матрицы должно быть число целое число

· «начальная» и «конечная» вершины должны быть целым числом, присутствовать в графе и не быть равными одна другой; программа допускает инициализацию вершин в обратном порядке (от большей к меньшей)

· весом ребра должно быть целое число

Программа отдельно рассматривает особые случаи инициализации графа

· граф нулевого размера (граф не существует)

· граф единичного размера (в графе одна вершина)

· граф, в котором все вершины не связаны (матрица смежности проинициализирована нулями)

· граф, в котором «начальная» и/или «конечная» вершина не связаны ни с одной другой вершиной (пути нет)

5. Отладка и тестирование

№ теста	Входные данные	Ожидаемый результат	Подтверждение
1	ввод size
1.1	-8	«Size is incorrect» (прерывание программы)	+
1.2	qwerty	«Size is incorrect» (прерывание программы)	+
1.3	5	Передается значение «5»	+
2.	ввод vertices
2.1	-8 3	«Vertices is incorrect» (прерывание программы)	+
2.2	qw erty	«Vertices is incorrect» (прерывание программы)	+
2.3	3 3	«Vertices is incorrect» (прерывание программы)	+
2.4	(size = 3) 4 5	"The graph doesn't have these vertices» (прерывание программы)	+
2.5	3 1	Передается значение: «1 3»	+
2.6	1 3	Передается значение: «1 3»	+
3	Особые случаи
3.1	size = 1	«There is one vertic in the graph» (прерывание программы)	+
3.2	size = 0	«Graph does not exist» (прерывание программы)	+
3.2	0 0 4 0 0 0 4 0 0 2 3	«No distance» (прерывание программы)	+
3.3	0 2 0 2 0 0 0 0 0 1 3	«No distance» (прерывание программы)	+
3.4	0 0 0 0 0 0 1 2	«No distance» (прерывание программы)	+
4	корректный ввод всех данных
4.1	size = 6 0 7 9 0 0 14 7 0 10 15 0 0 9 10 0 11 0 2 0 15 11 0 6 0 0 0 0 6 0 9 14 0 2 0 9 0 vertices: 1 5	The shortest distance from 1 to 5: 20	+
4.2	size = 5 0 3 6 4 0 3 0 2 5 0 6 2 0 0 1 4 5 0 0 3 0 0 1 3 0 vertices: 3 5	The shortest distance from 1 to 5: 1	+



Заключение

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



Список использованной литературы

1. Павловская Т.А. С/С++. Программирование на языке высокого уровня. -СПб.: Питер, 2002 - 464с

2. Стенли Липпман - Язык программирования C++. Базовый курс, 5-е изд.: Перевод с англ. - М.: ООО “И.Д. Вильямс”, 2017. - 1120 с.

3. Шилдт Г. С++: базовый курс, 3-е издание. : Пер. с англ. - М. : Издательский дом «Вильямс», 2010. - 624с.

4. http://cppstudio.com

5. https://habrahabr.ru

6. http://ci-plus-plus-snachala.ru



Приложения

Приложение 1

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

graph.cpp:

#define _CRT_SECURE_NO_WORNINGS

#include <iostream>

#include <stdlib.h>

#include <stdio.h>

#define Graph G

#define minimum_distance d

#define posited_vertices v

int main() {

try {

const int INF = INFINITY; //недостижимое число

int size;

std::cout << "Enter the number of vertices in the graph:\n";

std::cin >> size;

if (!std::cin || size < 0)

throw "Size is incorrect.\n";

if (size == 1)

throw "There is one vertic in the graph.\n";

if (size == 0)

throw "Graph does not exist.\n";

int **G = new int *[size]; //масив с динамической памятью

for (int i(0); i < size; i++) {

*(G + i) = new int[size];

}

int *d = new int[size];

bool *v = new bool[size];

int temp = 0;

int min = 0;

int minIndex = 0;

system("cls");

int v1, v2;

std::cout << "Enter two vertices:\n";

std::cin >> v1 >> v2;

if (!v1 || !v2 || v1 <= 0 || v2 <= 0 || v1==v2)

throw "Vertices are incorrect.\n";

if (v1 > size || v2 > size)

throw "The graph doesn't have these vertices.\n";

if (v1 > v2)

std::swap(v1, v2);

system("cls");

//Инициализация матрицы связей

for (int i(0); i < size; i++) {

G[i][i] = 0;

for (int j(i + 1); j < size; j++) {

//std::cout << "Enter the distance " << i + 1 << "--->" << j + 1 << std::endl;

temp = rand() % 10;

G[i][j] = temp;

G[j][i] = temp;

/*std::cin >> temp;

if (!std::cin || temp < 0)

throw "Distance is incorrect.\n";

G[i][j] = temp;

G[j][i] = temp;*/

}

}

temp = 0;

system("cls");

//Вывод матрицы связей на экран

std::cout << "\nInputed matrix:\n";

for (int i(0); i < size; i++) {

for (int j(0); j < size; j++)

std::cout << G[i][j] << " \t ";

std::cout << std::endl;

}

std::cout << std::endl;

int count = 0;

for (int i(0); i < size; i++) {

for (int j(0); j < size; j++) {

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

count++;

}

}

if (count == size*size)

throw "No distance.\n";

//int count1 = 0;

count = 0;

for (int i(0); i < size; i++) {

if (G[v1 - 1][i++] == 0)

count++;

}

if (count == size-1)

throw "No distance.\n";

count = 0;

for (int i(0); i < size; i++) {

if (G[v2 - 1][i++] == 0)

count++;

}

if (count == size - 1)

throw "No distance.\n";

//Инициализация вершин и растояний

for (int i(0); i < size; i++) {

d[i] = INF;

v[i] = 0;

}

d[v1 - 1] = 0;

//Шаг алгоритма

do {

minIndex = INF;

min = INF;

for (int i(0); i < size; i++) {

if (v[i] == 0 && d[i] < min) {

min = d[i];

minIndex = i;

}

}

//Добавляем найденный минимальный вес к текущему весу вершины и сравниваем с текущим минимальным весом вершины

if (minIndex != INF) {

for (int i(0); i < size; i++) {

if (G[minIndex][i] > 0) {

temp = min + G[minIndex][i];

if (temp < d[i])

d[i] = temp;

}

}

v[minIndex] = 1;

}

}

while (minIndex < INF);

//Вывод найденного пути на экран

std::cout << std::endl;

std::cout << "The shortest distance from " << v1 << " to " << v2 << " = " << d[v2 - 1] << std::endl;

}

catch (const char *error) {

std::cout << error;

}

system("pause");

return 0;

}



Приложение 2

Протоколы отладки

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

Затем пользователь вводит номер «начальной» и «конечной» вершины.

После ввода размера матрицы и интересующих вершин, пользователь последовательно вводит элементы массива(вес ребер). Стоит отметить, что пользователю не придется вводить один и тот же вес для двух «противоположных» вершин, так как программа сделает это самостоятельно.

Далее в консоли выводится полученная матрица и расстояние между заданными вершинами.



Приложение 3

Распечатки слайдов презентации

Размещено на Allbest.ru

...