Нахождение кратчайшего пути методом Дейкстры
Разработка программного обеспечения для решения задач поиска кратчайшего пути между вершинами графа на языке программирования Delphi с помощью алгоритма Дейкстры. Достоинства динамических массивов, понятия теории графов, представление графов на ЭВМ.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 07.06.2011 |
| Размер файла | 357,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Введение
Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается. Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии), также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др.
Предметом курсовой работы является графы, с помощью которых могут быть описаны многие структуры, представляющий практический интерес в математике и информатике.
Целью работы является разработка программного обеспечения для решения задач поиска кратчайшего пути между вершинами графа.
План работы:
- рассмотрение основных сведений о графах;
- рассмотрение алгоритма Дейкстры для нахождения кратчайшего пути между 2 вершинами;
- описать представление графов на ЭВМ;
- разработка программного продукта на языке программирования Delphi, реализующий алгоритм Дейкстры поиска кратчайшего пути между вершинами графа.
Большое значение в теории графов имеют алгоритмические вопросы. Для графов с конечным множеством вершин и ребер, как правило, проблема существования алгоритма решения задач, в том числе экстремальных, решается положительно. Решение многих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допустимых вариантов. Однако таким способом удается решить задачу только для графов с небольшим числом вершин и ребер. Поэтому существенное значение для теории графов имеет построение эффективных алгоритмов, находящих точное или приближенное решение. Для некоторых задач такие алгоритмы построены, например, для установления планарности графов, определения изоморфизма деревьев, нахождения максимального потока.
1. Описание алгоритма Дейкстры
1.1 Сведения о графах
Граф G задается множеством вершин х1, х2,…, хn. (которое обозначается через Х) и множеством линий (ребер) а1, а2,…, аm. (которое обозначается символом А), соединяющих между собой все или часть этих вершин в соответствии с рисунком 1. Таким образом, граф G полностью задается (и обозначается) парой (Х, А).
Рисунок 1 - Граф G
Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом в соответствии с рисунком 2.
Рисунок 2 - Ориентированный граф
Например, если дорога имеет не двух-, а одностороннее движение то направление этого движения будет показано стрелкой. Если ребра не имеют ориентации, то граф называется неориентированным в соответствии с рисунком 3.
Рисунок 3 - Неориентированный граф
В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т.е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рисунке 2 обозначение (х1, х3) относится к дуге а1. Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает как между собой связаны вершины. Соответствие Г называется отображением множества Х в Х, а граф в этом случае обозначается парой G=(Х, Г). Так, например, для графа на рисунке 2: Г (х1)={х2, х3}, т.е. вершины х2 и х3 являются конечными вершинами дуг, у которых начальной вершиной является вершина х1.
На рисунке 3: Г (х1)={х2, х4, х5}, (неориентированное ребро представляется как две противоположно направленные дуги, соединяющие те же самые вершины.) Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Так, на рисунке 4 последовательности дуг являются путями.
а6, а5, а9, а8. (1)
а1, а6, а5, а9. (2)
а1, а6, а5, а9, а10, а6. (3)
Рисунок 4 - Граф H
Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например приведенные выше пути (1) и (2) являются орцепями, а путь (3) не является таким, т. к. дуга а6 в нем используется дважды. Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2) является простой орцепью, а пути (1) и (3) - нет. Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер д1, д2,…, дq, в которой каждое ребро аq за исключением первого и последнего ребер, связано с ребрами аi-1 и аi+1 своими концевыми вершинами. Последовательности дуг:
д2, д4, д8, д10 (4)
д2, д7, д8, д4, д3, (5)
д10, д7, д4, д8, д7, д2. (6)
В графе, изображенном на рисунок. 1.4, являются маршрутами; две точки над символом дуги означают, что ее ориентацией пренебрегают, т.е. дуга рассматривается как неориентированное ребро. Также путь или маршрут можно изображать последовательностью вершин. Например, путь (1) будет выглядеть следующем образом: х2, х5, х4, х3, х5, х6. Иногда дугам графа приписываются числа, называемые весом, стоимостью, или длиной этой дуги. В этом случае граф называется графом со взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным. При рассмотрении пути µ представленного последовательностью дуг (д1, д2,…, дq), за его вес принимается число l(µ), равное сумме весов всех дуг, входящих в µ, т.е.
(7)
Пусть дан граф G=(Х, Г), дугам которого приписаны веса (стоимости / длины), задаваемые матрицей С = [cij].
Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины sx до заданной конечной вершины tx, при условии, что такой путь существует tR(s) (здесь R(s) - множество, достижимое из вершины s) и все циклы в графе имеют неотрицательный суммарный вес. Так как если в графе будет присутствовать цикл с отрицательным суммарным весом и хi - некоторая его вершина, то, двигаясь от s к хi, обходя этот цикл достаточно большое число раз и попадая, наконец в t, получится путь со сколь угодно малым (> ?) весом. Таким образом, в этом случае кратчайшего пути не существует. Так что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса. Следующие задачи являются непосредственными обобщениями сформулированной выше задачи о кратчайшем пути:
1. Для заданной начальной вершины s найти кратчайшие пути между s и всеми другими вершинами хiX.
2. Найти кратчайшие пути между всеми парами вершин.
Почти все методы, позволяющие решить задачу о кратчайшем (s-t) - пути, дают также (в процессе решения) и все кратчайшие пути от s к хi. Таким образом, они позволяют решить задачу с небольшими дополнительными вычислительными затратами. С другой стороны, задача 1 может быть решена либо n-кратным применением алгоритма задачи 2, причем на каждом шаге в качестве начальной вершины s берутся различные вершины, либо однократным применением специального алгоритма.
Наиболее распространенные методы их решения - это использование алгоритма Дейкстры (для нахождения кратчайшего пути между двумя вершинами), алгоритма Флойда (для нахождения кратчайших путей между всеми парами вершин) и алгоритма Йена (для нахождения k - кратчайших путей в графе).
1.2 Алгоритм Дейкстры. Доказательство корректности алгоритма
кратчайший путь вершина дейкстра
Каждой вершине из V сопоставляем метку - минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово - на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин - бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Рассматриваются всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, называют соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменяем значение метки полученным значением длины. Рассмотрев всех соседей, помечаем вершину u как посещенную и повторяем шаг алгоритма.
Доказательство корректности алгоритма
Обозначения:
w[ij] - вес (длина) ребра ij.
a - начальная вершина.
U - множество посещенных вершин.
d[u] - по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u.
p[u] - по окончании работы алгоритма содержит кратчайший путь из a в u.
Пусть l(v) - длина кратчайшего пути из вершины a в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d(z)=l(z).
Первой посещается вершина a. В этот момент d(a)=l(a)=0.
Шаг. Пускай мы выбрали для посещения вершину z ? a. Докажем, что в этот момент d(z) = l(z). Для начала отметим, что для любой вершины v, всегда выполняется d(v)?l(v) (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P - кратчайший путь из a в z, y - первая непосещённая вершина на P, x - предшествующая ей (следовательно, посещённая). Поскольку путь P кратчайший, его часть, ведущая из a через x в y, тоже кратчайшая, следовательно, l(y)=l(x)+w(xy). По предположению индукции, в момент посещения вершины x выполнялось d(x)=l(x), следовательно, вершина y тогда получила метку не больше чем d(x)+w(xy)=l(x)+w(xy)=l(y) (если существует k, такое что l(k) + w(ky) < l(x) + w(xy) то x не принадлежит P). Следовательно, d(y)=l(y). С другой стороны, поскольку сейчас мы выбрали вершину z, её метка минимальна среди непосещённых, то есть d(z)?d(y)=l(y)?l(z). Комбинируя это с d(z) ?l(z), имеем d(z)=l(z), что и требовалось доказать.
Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент d=l для всех вершин.
1.3 Рассмотрение алгоритма Дейкстры на примере
Рассмотрим выполнение алгоритма на примере графа показанного на рисунке 5. Пусть требуется найти расстояния от 1-й вершины до всех остальных.
Рисунок 5 - Пример графа
Кружками обозначены вершины, линиями - пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» - длина пути. Рядом с каждой вершиной красным обозначена метка - длина кратчайшего пути в эту вершину из вершины 1, как показано на рисунке 6.
Рисунок 6 - Инициализация алгоритма
Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6, что можно видеть на рисунке 7.
Рисунок 7
Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-ой в 2-ую, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7, которая отмечена на рисунке 8.
Рисунок 8
Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й, как показано на рисунке 9.
Рисунок 9
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра). Вычеркиваем её из графа, чтобы отметить, что эта вершина посещена, в соответствии с рисунком 10.
Рисунок 10
Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7, как видно из рисунка 11.
Рисунок 11 - Выбор вершины 2
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.
Первый (по порядку) сосед вершины 2 - вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.
Следующий сосед вершины 2 - вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется, что показывается на рисунке 12.
Рисунок 12
Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-ой вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку 22<?, устанавливаем метку вершины 4 равной 22, что видно на рисунке 13.
Рисунок 13
Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную, в соответствии с рисунком 14.
Рисунок 14
Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим результаты в соответствии с рисунком 15.
Рисунок 15 - Результаты после шага 3
Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку, рисунки 16, 17, 18 соответственно.
Рисунок 16 - Результаты после шага 4
Рисунок 17 - Результаты после шага 5
Рисунок 18 - Результат выполнения алгоритма
Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на рисунке 18: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.
2. Программная реализация алгоритма Дейкстры на ЭВМ
2.1 Внутреннее представление графов
Существуют различные способы внутреннего представления графов в оперативной памяти ЭВМ, в том числе в виде списков (массивов) вершин и ребер, списков (массивов) смежности, матриц смежности, а также в виде комбинаций этих структур хранения. Выбор внутреннего представления оказывает решающее влияние на эффективность выполнения различных операций над графами и во многом определяет «технологию» использования той или иной библиотеки в прикладных программах.
Ниже перечисленные структуры хранения графов будут рассмотрены более подробно, но перед этим необходимо сделать следующее замечание. В теории графов вершины и ребра графов, как правило, лишены индивидуальности: при таком подходе граф можно задать, например, булевской матрицей смежности, где логическая единица на пересечении i-ой строки и j-го столбца означает существование ребра (или дуги) между i-ой и j-ой вершинами графа. В то же время, во всех рассматриваемых библиотеках вершины и ребра графа считаются уникальными объектами (здесь термин «объект» употребляется в контексте объектно-ориентированного программирования), которые различаются, по крайней мере, тем, что каждый из них занимает отдельный участок в оперативной памяти ЭВМ. Объект-вершина может содержать или не содержать какие-либо данные; объект-ребро содержит, как минимум, указатели на инцидентные ему вершины. Если подходить с технологической точки зрения, то наличие уникальных объектов-вершин и объектов-ребер повышает удобство реализации и эффективность многих алгоритмов (хотя и неэкономично в смысле расхода оперативной памяти). Существует и более фундаментальная причина: при решении прикладных задач вершины графа, а иногда и его ребра, соответствуют реальным объектам предметной области. Таким образом, структуры хранения графов в объектно-ориентированной библиотеке для работы с графами обеспечивают хранение не только «математического» графа, но и объектов, представляющих вершины и ребра этого графа. Еще одно замечание необходимо сделать относительно использования списков и / или массивов: эти структуры данных будут считаться взаимозаменяемыми, пока изложение не коснется конкретных библиотек.
Основные структуры хранения графов на ЭВМ:
– Списки вершин и ребер;
– Списки смежности;
– Матрицы смежности;
Рассмотрим их более подробно.
Списки вершин и ребер. Граф представляется в виде двух списков, один из которых содержит указатели на его вершины, второй - на ребра (как всегда, каждое ребро хранит в себе указатели на инцидентные ему вершины). Данная структура хранения обеспечивает эффективное добавление в граф вершин и ребер, а также итерацию по вершинам и ребрам. В то же время, это представления неудобно, когда необходимо определить ребра, инцидентные заданной вершине графа.
Списки смежности. Граф представляется списком входящих в него вершин. В свою очередь, каждая вершина содержит список инцидентных ей ребер (или списки входящих и исходящих дуг в случае орграфов). Данное представление обеспечивает эффективное добавление в граф вершин и ребер, итерацию по вершинам графа и доступ к ребрам, инцидентным заданной вершине, но не поддерживает итерацию по ребрам графа.
Матрицы смежности. Граф задается квадратной матрицей размерности NxN, где N - количество вершин в графе; на пересечении i-го столбца и j-ой строки матрицы находится либо указатель на ребро, соединяющее вершины i и j, если эти вершины инцидентны, либо nil, если они не инцидентны. Вершины могут либо храниться в отдельном списке, либо только в составе инцидентных им ребер (в случае связных графов). Это представление удобно для реализации некоторых алгоритмов, но не обеспечивает эффективное добавление и удаление вершин. Кроме того, оно является самым неэкономичным по расходу памяти (за исключением графов, в которых количество ребер значительно превышает количество вершин).
Достоинством динамических массивов является быстрый доступ к элементам по индексу. Наиболее «дорогой» операцией при использовании динамических массивов является добавление элемента, поскольку в худшем случае для этого требуется выделить новый блок памяти увеличенного размера, скопировать содержимое старого блока памяти в новый и освободить старый блок, причем, по крайней мере, этап копирования имеет сложность O(n).
2.2 Программная реализация алгоритма Дейкстры
Для хранения вершин и весов ребер используется матрица смежности M. В i-ой строке, в j-ом столбце матрицы содержится вес ребра, если же вершины не соединены, присваивается значение 0. Количество вершин определяется максимальным количеством строк или столбцов матрицы минус количество симметричных нулевых строк (столбцов).
В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом. Массив флагов заполняется нулями. Затем запускается основной цикл. На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 d[i]=?. Последний случай возможен тогда и только тогда, когда граф G не связан.
Заключение
Результаты и методы теории графов применяются при решении транспортных задач о перевозках, для нахождения оптимальных решений задачи о назначениях, для выделения «узких мест» при планировании и управлении разработок проектов, при составлении оптимальных маршрутов доставки грузов, а также при моделировании сложных технология, процессов, в построении различных дискретных устройств, в программировании и т.д.
В теории графов существуют специфические методы решения экстремальных задач. Один из них основан на теореме о максимальном потоке и минимальном разрезе, утверждающей, что максимальный поток, который можно пропустить через сеть из вершины U в вершину V, равен минимальной пропускной способности разрезов, разделяющих вершины U и V. Были построены различные эффективные алгоритмы нахождения максимального потока.
В ходе выполнения данной курсовой работы были рассмотрены основные понятия теории графов, описано представление графов на ЭВМ, описан алгоритм Дейкстры, проведено доказательство корректности алгоритма, разобран пример работы алгоритма, выполнена программная реализация алгоритма в среде программирования Delphi.
Список литературы
1. Белов, А.В. Теория Графов, Москва, «Наука», 1968. - 459 c.
2. Смольяков, Э.Р. Введение в теорию графов. М.: МГТУ, 1992. - 373 c.
3. Березина, Л.Ю. Графы и их применение. - М.: Просвещение, 1979. - 323 c.
4. Новиков, Ф.А. Дискретная математика для программистов: Учебник для вузов, Спб, «Питер», 1 издание, 2004. - 443 c.
5. Исмагилов, Р.С. Материалы к практическим занятиям по курсу: Дискретная математика по теме: Алгоритмы на графах / Р.С. Исмагилов, А.В. Калинкин - М.: МГТУ, 1995. - 123 c.
Приложение А
Листинг программы
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, ExtCtrls, Grids, StdCtrls;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Image: TImage;
Button1: TButton;
Button2: TButton;
Edit1: TEdit;
Button3: TButton;
ListBox1: TListBox;
Edit2: TEdit;
Label1: TLabel;
Label2: TLabel;
Edit3: TEdit;
ListBox2: TListBox;
Label3: TLabel;
procedure Button1Click (Sender: TObject);
procedure Button2Click (Sender: TObject);
procedure Button3Click (Sender: TObject);
procedure Edit1KeyPress (Sender: TObject; var Key: Char);
procedure FormCreate (Sender: TObject);
procedure Edit2Change (Sender: TObject);
private
{Private declarations}
public
{Public declarations}
end;
const max=12;
NumbChars: SET OF CHAR = ['0'..'9'];
var
Form1: TForm1; n:integer; a1:array [1..max, 1..max] of integer; d:array [1..max] of longint;
implementation
{$R *.dfm}
function koorx (i:integer):integer;
begin
result:=round (sin(i*2*pi/n)*130);
end;
function koory (i:integer):integer;
begin
result:=round (cos(i*2*pi/n)*130);
end;
function vivchx (i:integer):integer;
begin
if koorx(i)>0 then
result:=koorx(i)+20
else
if koorx(i)<0 then if n mod 4=0 then result:=koorx(i) - 25 else result:=koorx(i) - 20
else
if koorx(i)=0 then result:=koorx(i);
end;
function vivchy (i:integer):integer;
begin
if koory(i)>0 then
result:=koory(i)+20
else
if koory(i)<0 then result:=koory(i) - 30
else
if koory(i)=0 then result:=koory(i);
end;
procedure TForm1. Button1Click (Sender: TObject);
var z, k, q, i, j:integer; nado:array [1..max] of boolean;
a:array [1..max, 1..max] of integer; s, ps:string;
kr:array [1..max] of integer; nado1:boolean;
begin
q:=StrToIntDef (Edit1. Text, 1);
if (q < 1) or (q > n) then q:= 1;
k:=StrToIntDef (Edit3. Text, 1);
if k=q then if q=n then k:=k-1 else k:=k+1;
if (k < 1) or (k > n) then k:= n;
if k>q then k:=k-2;
image. Picture:=nil;
for i:=1 to n do
nado[i]:=false;
for i:=0 to n-1 do
for j:=0 to n-1 do begin
if stringgrid1. Cells [i, j]='' then
a [i+1, j+1]:=0
else a [i+1, j+1]:=strtoint (stringgrid1. Cells [i, j]);
if a [i+1, j+1]<>0 then nado [i+1]:=true;
end;
for i:=1 to n do
if nado[i] then nado1:=true;
if nado1 then
begin
s:=listbox2. Items. Strings[k];
z:=1;
for i:=2 to length(s) do
begin
if (s[i] in numbchars) then
if (s [i+1] in numbchars) then begin kr[z]:=StrToInt (s[i])*10+StrToInt (s[i+1]) end
else if not (s[i-1] in numbchars) then begin kr[z]:=strtoint (s[i]); z:=z+1; end; end;
or i:=1 to n do
for j:=i+1 to n do
if a [i, j]<>0 then
begin
image. Canvas. MoveTo (koorx(i)+170, koory(i)+170);
image.canvas. LineTo (koorx(j)+170, koory(j)+170); end;
if edit3. Text<>'' then
for i:=1 to z do
begin
image. Canvas. Pen. Color:=clred;
image. Canvas. Pen. Width:=2;
if i=1 then image. Canvas. MoveTo (koorx(kr[1])+170, koory (kr[1])+170);
if (i<>1) and (i<z) then image. Canvas. LineTo (koorx(kr[i])+170, koory (kr[i])+170);
image. Canvas. Pen. Color:=clblack;
end;
for i:=1 to n do
begin
image. Canvas. Pen. Width:=2;
if nado[i] then begin
if i=q then
begin //начальная вершина
image. Canvas. Pen. Color:=clred;
image.canvas. Ellipse (koorx(i) - 15+170, koory(i)+15+170, koorx(i)+15+170, koory(i) - 15+170);
image. Canvas. TextOut (koorx(i)+165, koory(i)+165, inttostr(i));
image. Canvas. Pen. Color:=clblack;
end else
if (edit3. Text<>'') and (i=strtoint (edit3. Text)) then begin //конечная вершина
image. Canvas. Pen. Color:=clblue;
image.canvas. Ellipse (koorx(i) - 15+170, koory(i)+15+170, koorx(i)+15+170, koory(i) - 15+170);
image. Canvas. TextOut (koorx(i)+165, koory(i)+165, inttostr(i));
image. Canvas. TextOut (vivchx(i)+170, vivchy(i)+170, inttostr (d[i]));
image. Canvas. Pen. Color:=clblack;
end
else
begin
image.canvas. Ellipse (koorx(i) - 15+170, koory(i)+15+170, koorx(i)+15+170, koory(i) - 15+170);
image. Canvas. TextOut (koorx(i)+165, koory(i)+165, inttostr(i));
image. Canvas. TextOut (vivchx(i)+170, vivchy(i)+170, inttostr (d[i]));
end; end; end; end; end;
procedure TForm1. Button2Click (Sender: TObject); //заполнение матрицы
var i, j:integer;
begin
Randomize;
for i:= 0 to n - 1 do StringGrid1. Cells [i, i]:='0';
for i:= 0 to n - 1 do
for j:= i + 1 to n - 1 do
begin
StringGrid1. Cells [i, j]:= IntToStr (Random(30));
StringGrid1. Cells [j, i]:= StringGrid1. Cells [i, j];
a1 [i+1, j+1]:=strtoint (StringGrid1. Cells [i, j]);
a1 [i+1, j+1]:=strtoint (StringGrid1. Cells [j, i]); end; end;
procedure TForm1. Button3Click (Sender: TObject); //Алгоритм Дейкстры
var
p:array [1..max] of string;
a:array [1..max, 1..max] of longint;
b, nado:array [1..max] of boolean;
k, q, i, j, m, v, sh: integer;
begin sh:=1;
q:= StrToIntDef (Edit1. Text, 1);
if (q < 1) or (q > n) then q:= 1;
k:= StrToIntDef (Edit3. Text, 1);
if (k < 1) or (k > n) then q:= 6;
for i:=1 to n do
nado[i]:=false;
p[q]:=inttostr(q);
for i:= 1 to n do
for j:= 1 to n do begin
if stringgrid1. Cells [i-1, j-1]='' then a [i, j]:=0 else begin
a [i, j]:=StrToIntDef (StringGrid1. Cells [i - 1, j - 1], -1);
if a [i, j]<>0 then nado[i]:=true;
end; end;
fillchar (b, sizeof(b), 0);
fillchar (d, sizeof(d), 10000);
d[q]:= 0;
for i:=1 to n do
begin m:=1000;
for j:=1 to n do
if ((d[j] <= m) and (not b[j])) then
begin m:=d[j]; v:=j; end;
b[v]:= true; for j:=1 to n do
if ((a [j, v]<>0) and (not b[j]) and (d[v]+a [j, v]<d[j])) then
begin d[j]:=d[v]+a [j, v];
if q<>j then p[j]:=p[v]+'->'+inttostr(j) end; end;
ListBox1. Clear;
if nado[q] then for i:= 1 to n do
if (i<>q) and (nado[i]) then
ListBox1. Items. Append (IntToStr(q) + ' -> ' + IntToStr(i) + ': ' + IntToStr (d[i]));
ListBox2. Clear; if nado[q] then
for i:= 1 to n do
if (i<>q) and (nado[i]) then
ListBox2. Items. Append (inttostr(i)+': '+p[i]); end;
procedure TForm1. Edit1KeyPress (Sender: TObject; var Key: Char);
begin case key of
'0'..'9',#8,#13:key:=key
else key:=#0; end; end;
procedure TForm1. FormCreate (Sender: TObject);
begin if edit2. Text<>''
then n:=strtoint (edit2.text)
else n:=6; stringgrid1. ColCount:=n;
stringgrid1.rowCount:=n;
stringgrid1. Width:=n*31+3;
stringgrid1.height:=n*31+3;
listbox1. Left:=31*n+22;
listbox2. Left:=31*n+22;
image. Left:=31*n+142;
button1. Left:=31*n+126; end;
procedure TForm1. Edit2Change (Sender: TObject);
begin if edit2. Text<>''
then if strtoint (edit2.text)>12 then begin n:=12; edit2. Text:='12'; end else n:=strtoint (edit2.text)
else n:=6; stringgrid1. ColCount:=n;
stringgrid1.rowCount:=n;
stringgrid1. Width:=n*31+3;
stringgrid1.height:=n*31+3;
if n>6 then begin listbox1. Left:=31*n+22;
listbox2. Left:=31*n+22;
image. Left:=31*n+126;
button1. Left:=31*n+126; end
else begin listbox1. Left:=31*6+22;
listbox2. Left:=31*6+22;
image. Left:=31*6+126;
button1. Left:=31*6+126;
end; end; end.
Размещено на Allbest.ru
Подобные документы
Разработка алгоритма реализации на ЭВМ процесса поиска кратчайшего пути в графе методом Дейкстры. Программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа. Проверка работоспособности программы на тестовых примерах.
реферат [929,8 K], добавлен 23.09.2013История и термины теории графов. Описание алгоритма Дейкстры. Математическое решение проблемы определения кратчайшего расстояния от одной из вершин графа до всех остальных. Разработка программы на объектно-ориентированном языке программирования Delphi 7.
контрольная работа [646,9 K], добавлен 19.01.2016Теория графов и её применения. Разработка программного продукта для решения задач нахождения минимального пути. Анализ надежности и качества ПП "метода Дейкстры". Математическая модель задачи. Алгоритмы Дейкстры на языке программирования Turbo Pascal.
курсовая работа [1,6 M], добавлен 26.03.2013Графы: определения, примеры, способы изображения. Смежные вершины и рёбра. Путь в ориентированном и взвешенном графе. Матрица смежности и иерархический список. Алгоритм Дейкстры - алгоритм поиска кратчайших путей в графе. Работа в программе "ProGraph".
презентация [383,8 K], добавлен 27.03.2011Задача о кратчайшем пути как одна из важнейших классических задач теории графов. Общий обзор трех наиболее популярных алгоритмов для решения задачи о кратчайшем пути. Написание программы, которая реализует алгоритм Дейкстры и алгоритм Форда-Беллмана.
курсовая работа [2,1 M], добавлен 23.06.2014Алгоритмы, использующие решение дополнительных подзадач. Основные определения теории графов. Поиск пути между парой вершин невзвешенного графа. Пути минимальной длины во взвешенном графе. Понятие кратчайшего пути для графов с помощью алгоритма Флойда.
реферат [39,6 K], добавлен 06.03.2010История возникновения, основные понятия и теоремы теории графов. Способы предоставления графов в компьютере. Матрица смежности, инциденций, списки смежности и массив дуг. Программа определения кратчайшего пути в графах. Язык программирования Delphi.
курсовая работа [823,5 K], добавлен 24.11.2010Основные понятия и определения теории графов: теоремы и способы задания графа, сильная связность графов. Построение блок-схем алгоритма, тестирование разработанного программного обеспечения, подбор тестовых данных, анализ и исправление ошибок программы.
курсовая работа [525,6 K], добавлен 14.07.2012Алгоритм сортировки Шейкер: математическое описание задачи и описание алгоритма. Алгоритм покрытия: построение одного кратчайшего покрытия. Описание схемы и работы алгоритма на графах: нахождение кратчайшего пути. Контрольные примеры работы алгоритмов.
курсовая работа [43,8 K], добавлен 19.10.2010Разработка программы в среде Delphi для нахождения кратчайшего пути между стартом, лежащим в одной из вершин многоугольника, и финишем, находящимся на одной из сторон. Установка опорных точек, контроль целостности вводимых данных, методы решения задачи.
курсовая работа [778,8 K], добавлен 19.10.2010
