Проектный раздел
3.1 Описание алгоритма и структуры программы
Пусть на каком-то шаге уже помечено несколько вершин. Известны кратчайшие пути, ведущие из исходной вершины к помеченным. Для каждой из непомеченных вершин проделаем следующее:
Рассмотрим все дуги, ведущие из помеченных вершин в одну непомеченную. Каждая такая дуга является последней дугой на пути из исходной вершины в эту непомеченную.
Выберем из этих путей кратчайший. А затем выберем среди них самый короткий ко всем непомеченным вершинам, и пометим вершину, к которой он ведет.
Алгоритм завершится, когда будут помечены все достижимые вершины. В результате работы алгоритма Дейкстра строится Дерево кратчайших путей.
Для написания программы используется язык программирования С++. При написании программы использовалась среда MicrosoftVisualStudio.
Программа выводит минимальный путь между двумя указанными вершинами в графе и его длину.
При запуске программы на экран выводится поле для ввода данных (сам ориентированный граф и весы его дуг). Данные, введённые пользователем, представляют собой наглядное изображение ориентированного графа. По умолчанию длина пути из исходной вершины в конечную равна миллиарду, который принимается за бесконечность.
По нажатию кнопки «найти путь» включается функция алгоритма Дейкстра и найденный путь выводится в окне сообщений. Если пути между заданными точками не существует – выводится соответствующее сообщение.
3.2 Формальная постановка
Входные данные: взвешенный ориентированный граф, номера начальной и конечной вершины.
Выходные данные: кратчайший путь из начальной в конечную вершину, его длина.
3.3Описание использованных программных средств
Переменная |
Описание |
myPoint V[Max_N] |
Массив вершин графа(коодинаты вершины) |
int E[Max_N][Max_N] |
Массив ребер графа |
PointFstartpos,endpos |
Начальная и конечная точка ребра(вершины графа) |
intcena[Max_N][2] |
Массив значений - минимальное расстояние до вершины и предок |
multimap<int,int> m |
Словарь значений - минимальная цена среди текущих и номер его |
Таблица 1 - Описание переменных.
В программе были использованы следующие функции:
Double modul(myPointA,myPointB) – функция, которая возвращает расстояние между 2мя точками.
Void Deikstra(intA,intB) – функция, реализующая алгоритм Дейкстры.
Void DrawCena(intA,intB) – графическая процедура рисования цены дуги.
Void DrawGraph() – графическая процедура рисования графа.
Экспериментальный раздел
Тестирование при нормальных условиях
Нормальные условия – количество ребер меньше 100, цена ребра меньше 1000000000. Алгоритм выполняется успешно.
Рисунок 2 – Тестирование при нормальных условиях.
Рисунок 3 – Тестирование при нормальных условиях
Тестирование при экстремальных условиях
Экстремальные условия – длина дуги больше миллиарда. Как видно на рисунке 3, из за проверки на максимальную цену, дуга не создается.
Рисунок 3 – Тестирование при экстремальных условиях.
Экстремальные условия – координаты начала дуги и конца совпадают. Программа не может рисовать петли в графе, соответственно выводится сообщение об ошибке (это видно на рисунке 4).
Рисунок 4 – Тестирование при экстремальных условиях.
Заключение
В данной курсовой работе был изложен алгоритм Дейкстрадля решения задачи о нахождении кратчайших путей в графе и составлена программа.
В ходе выполнения работы были получены практические навыки решения задач с использованием графов и представлении их на ЭВМ, закреплен теоретический курс лекций по данному предмету.
Список использованных источников
1. Алгоритм Дейкстра [Электронный ресурс] // - режим доступа: http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
2. Хаханов В.И., Чумаченко С.В. Дискретная математика (теоретическое и практическое содержание курса).–Кафедра АПВТ, 2002
3. Ананий В. Левитин Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ. - М.: "Вильямс", 2006. - С.189-195.
4. Дейкстра Э. Дисциплина программирования. - М.: Мир, 1978. - С.275.
Приложение А - листингпрограммы
Объявление переменных, функций и констант:
#pragmaonce
#include<math.h>
#include"inputbox.h"//подключаетсяформа
#include<vector>
#include<map>//подключаем ассоциативный массив - содежит пары <ключ,значение> и сортирует автоматически по ключу
usingnamespace System::Drawing;
struct myPoint //создаемструктуру
{
float X,Y;
};
usingnamespace std;//используем стандартное пространство имен
constint Max_N=100;//максимальное количество вершин
myPoint V[Max_N];//Массив вершин графа(коодинаты вершины)
int E[Max_N][Max_N];//Массив ребер графа(1000000000-нет ребра, менее 1 млрд - ребро из i-ой вершины в j-ую заданной стоимости)
int N=0;//количество вершин
PointF startpos,endpos;//начальная и конечная точка ребра(вершины графа)
constdoubleR_min=8.0;//радиус точки обозначающей вершины графа
Процедура алгоритма Дейкстры:
void Deikstra(int A,int B)//реализация алгоритма Дейкстры
{
--A;//приводим номера вершин к отсчету с 0
--B;//
int i;
for (i=0;i<Max_N;i++)//присваиваем всем очень большое число - знак что их еще не посетили.
{
cena[i][0]=1000000000;
cena[i][1]=-1;
}
if (A<0||A>=N || B<0 || B>=N)//если номера вершин не существуют, завершаем работу процедуры
return;
m.clear();//очищаем список цен и вершин.
cena[A][0]=0;//достижимость вершины А равна нулю.
m.insert(make_pair(0,A));//и добавляем ее как текущую.
while (!m.empty())//и пока есть вершины для обновления
{
int k=(*m.begin()).second;//запоминаем номер вершины с самой маленькой ценой
m.erase(m.begin());//удаляем ее из списка
for(i=0;i<Max_N;i++)//и бежим по всем ребрам из этой вершины (К-ой)
if (E[k][i]<1000000000 &&//если есть ребро и..
cena[i][0]>cena[k][0]+E[k][i])//цена перехода из этой вершины меньше чем из другой то
{
cena[i][0]=cena[k][0]+E[k][i];//присваиваем цену минимальную
cena[i][1]=k;//и запоминаем из какой вершины пришли
m.insert(make_pair(cena[i][0],i));//добавляем в словарь цен и номеров вершин
}
}
Процедура рисования графа и цены возле дуги:
private: void DrawCena(int A,int B)//процедура рисования Цены возле ребра
{
double a,b;
a=(V[A].X+V[B].X)/2; //вычисляемсерединуребра
b=(V[A].Y+V[B].Y)/2;
double x,y,r=sqrt(pow(V[A].X-V[B].X,2)+pow(V[A].Y-V[B].Y,2));//длинуребра
x=(V[B].X-V[A].X)/r;//нормируем вектор
y=(V[B].Y-V[A].Y)/r;
a-=y*12;//и по середке со смещением пишем
b+=x*12;
g->DrawString(E[A][B].ToString(),l1->Font,(gcnew Pen(Color::Blue))->Brush,a,b);//ценуребра
x*=7;
y*=7;
a=V[B].X-x;
b=V[B].Y-y;
Pen^ p =gcnew Pen(Color::Black);
g->DrawLine(p,(float)a,(float)b,(float)a-x-y,(float)b-y+x);
g->DrawLine(p,(float)a,(float)b,a-x+y,b-y-x);
};
private: void DrawGraph()//процедурарисованияграфа
{
float r=R_min/2;//радиус точки "вершины"
this->g->FillRectangle((gcnew Pen(Color::White))->Brush,0,0,pictureBox1->Width,pictureBox1->Height);//заливаемвесьпикчербокс
for (int i=0;i<N;i++)// в цикле прорисовываем все вершины на полотне в виде кружков
g->DrawEllipse(p,V[i].X-r,V[i].Y-r,R_min,R_min);
for (int i=0;i<N;i++)//и по всему массиву ребер бежим
for (int j=0;j<N;j++)
if (E[i][j]<1000000000)//если есть ребро, то рисуем его:
{
g->DrawLine(p,ftoF(V[i]),ftoF(V[j]));//рисуем ребро из i-ой в j-ую вершину
g->DrawString((i+1).ToString(),l1->Font,p->Brush,V[i].X+4,V[i].Y+4);//ипишемномеравершин
g->DrawString((j+1).ToString(),l1->Font,p->Brush,V[j].X+4,V[j].Y+4);//ивторойномер.
DrawCena(i,j);
}
}
Процедуры обработки событий нажатия и опускания мыши:
private: System::Void pictureBox1_MouseDown(System::Object^ sender, System::Windows::Forms::MouseEventArgs^ e)
{ //событиеопусканиякнопкимыши
startpos= pictureBox1->PointToClient(MousePosition);//запоминаемпозициюуказателянабоксе
}
private: System::Void pictureBox1_MouseMove(System::Object^ sender, System::Windows::Forms::MouseEventArgs^ e)
{//событие перемещения мыши над боксом(картинкой)
DrawGraph();//перерисуемграф
if (startpos!= PointF(-1,-1))//и если существует точка начала ребра, то
{
this->g->DrawLine(p,startpos,pictureBox1->PointToClient(MousePosition));//проводим ребро до текущей позиции курсора
}
for (int i=0;i<N;i++)//бежим по всем вершинам и ...
if (modul(Ftof(pictureBox1->PointToClient(MousePosition)),V[i])<R_min/2.0)//если расстояние от указателя до вершины меньше заданного то
{
pictureBox1->Cursor = Cursors::Hand;//ставимкурсовввид "Руки"
break;//прерываемцикл
}
else
pictureBox1->Cursor = Cursors::Default;//иначеставимстандартныйкурсор
}
private: System::Void pictureBox1_MouseUp(System::Object^ sender, System::Windows::Forms::MouseEventArgs^ e)
{//событие отпускания мыши
if (startpos!= PointF(-1,-1))//если есть стартовая точка ребра то...
{
int n1=N;
endpos=pictureBox1->PointToClient(MousePosition);//вычисляем конечную точку ребра
if (modul(Ftof(endpos),Ftof(startpos))<R_min)
{
startpos=PointF(-1,-1);//убираем стартовую точку(начало ребра)
MessageBox::Show("Нельзя делать 'Петли'(начало и конец совпадает) в графе","Результат");
return;
}
int fl1=-1,fl2=-1;//номера конечной и начальной вершины для нового ребра
for (int i=0;i<N;i++)//пробегаем по циклу и ищем, есть ли совпадения со старыми вершинами
{
if (modul(Ftof(startpos),V[i])<R_min) fl1=i;//если начало совпадает с какой-то вершиной, то ставим ее туда
if (modul(Ftof(endpos),V[i])<R_min) fl2=i;//если конец ребра совпадает с какой-то вершиной, то ставим ее туда
}
if (fl1==-1) {V[N++]=Ftof(startpos);fl1=N-1;}//если не совпадает начало ни с какой старой вершиной, то делаем новую вершину
if (fl2==-1) {V[N++]=Ftof(endpos);fl2=N-1;}//если не совпадает конец ни с какой старой вершиной, то делаем новую вершину
if (E[fl1][fl2]<1000000000)//если есть уже ребро то
{
startpos=PointF(-1,-1);//убираем стартовую точку(начало ребра)
MessageBox::Show("Нельзя делать 'Кратные ребра'(такое ребро уже есть) в графе","Результат");
return;
}
else{
InputBox p;
p.ShowDialog(this);//показываем форму ввода цены
if (p.result)//и если не отмена, то
E[fl1][fl2]=Convert::ToInt32(p.textBox1->Text);//ставим в матрицу смежности что есть ребро такой то цены
else
N=n1;//иначе восстанавливаем количество вершин
}
startpos=PointF(-1,-1);//убираем стартовую точку(начало ребра)
}
}
ПроцедуравызоваалгоритмаДейкстры:
System::Void button1_Click(System::Object^ sender, System::EventArgs^ e)
{//
int i=Convert::ToInt32(maskedTextBox1->Text),j=Convert::ToInt32(maskedTextBox2->Text);//запоминаемномеравершин
Deikstra(i,j);//запускаемалгоритмДейкстры
if (cena[j-1][1]==-1)//если цена осталась отрицательна, то пути нету между вершинами
MessageBox::Show("Нет пути между этими вершинами!","Результат");
else
{
int k=j-1;//запоминаем вершину
DrawGraph();//рисуемграф
String^ Path ="";//
while (k!=i-1)//и пока не встретим начальную вершину, поднимаемся и прорисовываем от конечной
{
Path=(k+1).ToString()+" - "+Path;//заносим весь путь в стрчку через тире
k=cena[k][1];//переходя к предку текущей
}
Path=(i).ToString()+"-"+Path;//добавляем начальную вершину в начало списка
MessageBox::Show("Последовательность: "+Path +".""\nДлина пути = "+cena[j-1][0].ToString(),"Результат",MessageBoxButtons::OK);
}
}
|
|
|
|
|
|
|||||
|
|
|
|
|
||||||
Изм. |
Лист |
№ докум. |
Подп. |
Дата |
||||||
Разраб. |
|
|
|
Алгоритм Дейкстра |
Лит. |
Лист |
Листов |
|||
Пров. |
|
|
|
У |
|
|
2 |
|
||
|
|
|
|
ВСГТУ, |
||||||
Н. контр. |
|
|
|
|||||||
Утв. |
|
|
|
|||||||