Вершины графа пронумерованы от 1 до n. Граф G представлен матрицей смежности. Требуется найти длины кратчайших путей между всеми парами. Постановка задачи Настоящая курсовая работа моделирует логическую задачу, часть дискретный математика программа интерфейс Пусть дан граф Задача о кратчайшем пути состоит в нахождении кратчайшего пути от. Описание различных задач на графах, нахождение кратчайших путей. Язык программирования Delphi. Курсовой проект. По дисциплине: «Технология программирования». Тема: «Определение кратчайшего пути в графе». Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике. Работы, похожие на Реферат: Нахождение кратчайших путей в графе Алгоритм Йена. 1 Курсовой проект. По дисциплине: «Технология программирования». Тема: «Определение кратчайшего пути в графе». Нахождение кратчайших путей в графе 16. Программа определения кратчайшего пути в графе 19.

Анализ предметной области. Основные определения. Компьютерные средства для реализации задачи. Цель и задачи курсовой работы. Анализ задачи и методов ее решения.

Задача поиска выделенного кратчайшего пути. Алгоритм Дейкстры.

Нахождение кратчайшего пути. Годом возникновения теории графов единодушно считается год 1736, когда. Целью курсовой работы было изучить и реализовать на практике алгоритм Дейкстры и Флойда для нахождения кратчайших путей в графе.

Решения 2.1 Задача поиска выделенного кратчайшего пути 2.2 Алгоритм графа, в связи с этим свою актуальности приобретает нахождение путей.

Размер курсовой работы 16 страниц, содержит графические иллюстрации, список использованных источников. Зарегистрируйся или зайди через. Нахождение кратчайших путей в графе методом Флойда. Тип: Курсовая работа (Теория). Предмет: Математика. Все курсовые работы (теория) по математике ». Язык: Русский. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе.

Задача поиска всех кратчайших путей. Алгоритм Флойда. 3. Разработка программы. Характеристика программы и системные требования. Описание модульной структуры разработанной программы.

Описание диалога с пользователем. Контрольный пример. Заключение. Список литературы. Введение. В данной курсовой работе я рассмотрел решение одной из важнейших задач дискретной математики — нахождение кратчайшего пути между парами всех вершин в ориентированном и неориентированном графах, путем использования алгоритма Флойда.

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

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

Основные определения. Графом G= (X, U) будем называть совокупность двух конечных множеств; множества вершин X=.

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

Рисунок 1дискретная математика ориентированный граф. При этом вершины x, x называют концами (концевыми вершинами) ребра. В данном случае также говорят, что ребро (x, x) — соединяет вершины xи x.

Если пары вершин (x, x) в множестве U являются упорядоченными (т. Рисунок 2. При этом x — начало (начальная вершина) дуги, x — конец (конечная вершина) дуги. Говорят также, что дуга < x, x> исходит из вершины xи заходит в вершину x. Заметим, что < x, x> и < x, x> - это различные дуги в графе. При изображении орграфа дуги обозначаются стрелками, указывающими их ориентацию (направление).

Пара вершин (x, x) в графе может соединяться двумя или более ребрами (дугами одного направления). Отметим, что любой неориентированный граф можно представить в виде орграфа путем замены каждого его ребра двумя противоположно направленными дугами. Тогда граф G называется графом со взвешенным дугами.

Иногда веса (числа v) приписываются вершинам x графа, и тогда получается граф со взвешенными вершинами. Книгу Эсаулов Чернобыль Летопись Мертвого Города подробнее. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным.

Петлей называется дуга, начальная и конечна вершины которой совпадают. Примером петли является дуга u на рисунке 1.

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

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

Замкнутый путь называется контуром, замкнутый простой путь — простым контуром. Граф, не содержащий циклов, называют ациклическим. Число дуг, исходящих из вершины x ориентированного графа, называется полустепенью исхода вершины x и обозначается (x). Число дуг, заходящих в вершину x, называется полустепенью захода вершины x и обозначается (x). Существуют и другие способы определения графа, например с помощью матрицы смежности.

Пусть дан граф G (рисунок 3)Рисунок 3 — Граф GМатрицей смежности неориентированного графа G= (X, U) с n вершинами называется квадратная матрица, А порядка n, элементы которой определяются следующим образом: Для ориентированного графа: Следовательно, матрица смежности графа, изображенного на рисунку 3 имеет вид, в противном случае. Рисунок 4 — Матрица смежности графа GПетлям в матрице смежности соответствуют элементы, расположенные на главной диагонали. Матрица смежности полностью определяет структуру графа. Например, сумма всех элементов строки x матрицы дает полустепень исхода вершины x, а сумма элементов столбца x — полустепень захода вершины x. Множество столбцов, имеющих 1 в строке x, есть множество Г (x), а множество строк, которые имеют 1 в столбце x, совпадает с множеством Г (x).

Особенностями языка являются строгая типизация и наличие средств структурного (процедурного) программирования. Паскаль был одним из первых таких языков.

По мнению Н. Вирта, язык должен способствовать дисциплинированию программирования, поэтому, наряду со строгой типизацией, в Паскале сведены к минимуму возможные синтаксические неоднозначности, а сам синтаксис интуитивно понятен даже при первом знакомстве с языком. В настоящий момент пользуются популярностью такие версии языка как Turbo Pascal, Free Pascal и GNU Pascal. Продолжает использоваться и Borland Pascal. Развитием языка Borland Pascal является Object Pascal — версия языка Паскаль расширенная средствами объектно- ориентированного программирования. Последние версии Borland Pascal лежат в основе среды программирования Delphi . В феврале 1. 99. 4 года Турбо Паскаль был перенесен на операционную систему MS- DOS. На раннем этапе развития компьютеров IBM PC, Турбо Паскаль являлся одним из наиболее популярных языков разработки программного обеспечения — главным образом потому, что это было вполне серьезный компилятор, который, включая компилятор, редактор и все остальное, стоил всего $ 1.

Kb оперативной памяти. Под Windows — Турбо Паскаль был перенесен фирмой Borland в 1. А самая последняя версия Borland Pascal 7. Delphi, вышла в свет в 1.

Разработка Delphi началась в 1. После проведения beta- тестирования Delphi показали на «Software Development '9. И 1. 4 февраля 1.

США. В торговлю Delphi попала спустя 1. Язык программирования C++C++ был разработан в 1. Bell. Он считается наиболее подходящим языком для обновления систем, написанных на языке С. Изначально C++ был разработан, чтобы автору и его друзьям не приходилось программировать на ассемблере, C или других современных языках высокого уровня. Основным его предназначением было сделать написание хороших программ более простым и приятным для отдельного программиста. Плана разработки C++ на бумаге никогда не было; проект, документация и реализация двигались одновременно.

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

Язык С++ поддерживает наследование. Это значит, что можно объявить новый тип данных (класс), который является расширением существующего. Хотя язык С++ справедливо называют продолжением С и любая работоспособная программа на языке С будет поддерживаться компилятором С++, при переходе от С к С++ был сделан весьма существенный скачок.

Алгоритм Дейкстры . Постановка задачи Настоящая курсовая работа моделирует логическую задачу, состоящую из следующих частей: 1) Изучение конкретного раздела дискретной математики. Решение 5- ти задач по изученной теме с методическим описанием. Разработка и реализация в виде программы алгоритма по изученной теме. Разработка программного интерфейса.

Введение 2. 1 Теоретическая часть дискретный математика программа интерфейс Пусть дан граф G=(X, Г), дугам которого приписаны веса (стоимости), задаваемые матрицей C=. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s. X до заданной конечной вершины t. X, при условии, что такой путь существует, т. Здесь R(s) – множество, достижимое из вершины s.

Элементы cij матрицы весов C могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в G не было циклов с отрицательным суммарным весом. Если такой цикл Ф все же существует и xi – некоторая его вершина, то, двигаясь от s к xi, обходя затем Ф достаточно большое число раз и попадая наконец в t, мы получим путь со сколь угодно малым () весом. Таким образом, в этом случае кратчайшего пути не существует. Если, с другой стороны, такие циклы существуют, но исключаются из рассмотрения, то нахождение кратчайшего пути (простой цепи) между s и t эквивалентно нахождению в этом графе кратчайшего гамильтонова пути с концевыми вершинами s и t.

Это можно усмотреть из следующего факта. Если из каждого элемента cij матрицы весов C вычесть достаточно большое число L, то получится новая матрица весов C'=. Тогда кратчайший путь от s к t – с исключением отрицательных циклов – необходимо будет гамильтоновым, т. Так как вес любого гамильтонова пути с матрицей весов C' равен весу этого пути с матрицей весов C, но уменьшенному на постоянную величину (n- 1). Задача о нахождении кратчайшего гамильтонова пути намного сложнее, чем задача о кратчайшем пути.

Поэтому мы будем.