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

Граф - это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Если каждому ребру соответствует какое-либо число - вес, то граф называется взвешенным. Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом. Если ребра не имеют ориентации, граф называется неориентированным.Условие поставленной передо мной задачи выглядит следующим образом: Дан неориентированный граф с количеством вершин size и инициализированным весов ребер. Необходимо определить кратчайший путь из заданной вершины в заданную через вершины графа. И вывести на экран суммарный вес ребер, через которые проходит этот путь. 1) Метка вершины 1 полагается равной 0, метки остальных вершин - недостижимое большое число. Для вершины 2: длина пути в нее через вершину 1 равна сумме метки вершины 1 и длины ребра, соединяющих вершины 1 и 2Для представления графа я использовала двумерный массив типа int с выделяемой динамической памятью. Для хранения информации о минимальных расстояниях (метках) до проверяемых вершин в ходе работы алгоритма я создала одномерный массив типа int с выделяемой динамической памятью.Мой проект содержит в себе один файл «graph.cpp», в котором обозначены все используемые структуры данных, инициализирован двумерный массив смежности графа и прописан алгоритм поиска кратчайшего пути из заданной вершины в заданную.Для обозначения кратчайшего пути из одной вершины в другую используются метки, присвоенные каждой отдельной вершине. Метка представляет собой сумму всех ребер с минимальным весом, соединяющих одну вершину с другой. Результатом работы алгоритма будет метка, присвоенная «конечной» вершине. · «начальная» и «конечная» вершины должны быть целым числом, присутствовать в графе и не быть равными одна другой; программа допускает инициализацию вершин в обратном порядке (от большей к меньшей)1.1-8 «Size is incorrect» (прерывание программы) 1.2 qwerty «Size is incorrect» (прерывание программы) 2.1-8 3 «Vertices is incorrect» (прерывание программы) 2.4 (size = 3) 4 5 "The graph doesn"t have these vertices» (прерывание программы) 3.2 size = 0 «Graph does not exist» (прерывание программы) В ходе написания курсовой работы я научилась работать с графами в представлении языка С , усовершенствовала навыки работы с массивами (одномерными и двумерными), циклами (со счетчиком, с постусловием) и указателями.#define posited_vertices v int main() {try {const int INF = INFINITY; //недостижимое число int size; if (!std::cin || size <0) throw "Size is incorrect.

"; if (size == 1) throw "There is one vertic in the graph.

"; if (size == 0) throw "Graph does not exist.

"; if (v1 > size || v2 > size) throw "The graph doesn"t have these vertices.

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

Содержание

Введение

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

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

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

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

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

Заключение

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

Приложения

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

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

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

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

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

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

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

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

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