Теория графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
еров вершин, между которыми необходимо узнать путь. В случае, если начальная и конечная вершины совпадают, отображается соответствующее сообщение и работа программы завершается. В противном случае выполняется непосредственно алгоритм Дейкстры, схема которого приведена в приложении. Результатом программы является вывод на экран вершин, через которые проходит минимальный путь, а также вывод длины маршрута. Если пути между заданными точками не существует - выводится соответствующее сообщение.
Описание использованных программных средств
ПеременнаяТипОписаниеnintКоличество точек вершин графаi,jintСчётчикиpintНомер кратчайшего пути и наименьшей длины путиxnintНомер начальной точки (вершины)xkintНомер конечной точки (вершины)flag[11]intМассив, i-й элемент которого имеет значение 0, когда i-й путь и расстояние временные, и принимает значение 1, когда i-й путь и расстояние становятся постояннымиc[11][11]word (unsigned int)Массив i-j элемент которого содержит расстояние между i-й и j-й точками (вершинами) Замечание: 1. с[i][i]= 2. c[i][j]=c[j][i]s[80]charСтрочная переменная, которая содержит промежуточные значения путиpath[80][11]charМассив строк, который содержит пути Замечание: После прохождения обработки по алгоритму Дейкстры p-й элемент массива содержит кратчайший путь.l[11]word (unsigned int)Массив, который содержит длины путей (path) Замечание: После прохождения обработки по алгоритму Дейкстры p-й элемент массива содержит длину кратчайшего пути.
Кроме стандартных функций из библиотек iostream.h, string.h, stdio.h, conio.h были использованы также следующие функции.
word minim(word x, word y) - функция, которая возвращает минимальное из x и y.
int min(int n) - функция, которая возвращает номер элемента массива l[i] минимальной "неотмеченной" длиной пути(flag[i]=0).
3. Ручной просчёт задачи
Пусть дан граф, заданный матрицей весов:
Получаем, что путь из точки А в точку В: А, F, а длина пути равна 4.
. Тестирование программы
Заключение
При рассмотрении теории графов можно сделать вывод: решая задачу о нахождении города, для которого сумма расстояний до остальных городов минимальна, удобно было использовать теорию графов.
Цель данной работы достигнута: алгоритм и программа решения задачи составлен, правильность работы программы проверена.
Список литературы
1.Гапанович В.С., Гапанович И.В. Дискретная математика: Учебное пособие. Тюмень: ТюмГНГУ, 2002. - 187 с.
2.Дискретная математика для программистов / Ф.А. Новиков - СПб: Питер, 2000. - 304 с.
.Дискретная математика. Алгоритмы и программы: Учеб. пособие/Б.Н. Иванов. - М.: Лаборатория Базовых Знаний, 2003. - 288 с.
.Кормен Алгоритмы: построение и анализ / 1990.
Приложение
#include
#include
#include
#include
#include
#define word unsigned inti, j, n, p, xn, xk;flag[11];c[11][11], l[11];s[80], path[80][11];min(int n)
{i, result;(i=0;il[i])&&(!flag[i])) result=i;result;
}minim(word x, word y)
{(x<y) return x;y;
}main()
{n;(i=0;i<n;i++)(j=0;j<n;j++) c[i][j]=0;(i=0;i<n;i++)(j=i+1;j<n;j++)
{
cout<<"Vvedite rasstoyanie ot x"<<i+1<<" do x"<<j+1<<": ";
cin>>c[i][j];
}<<" ";(i=0;i<n;i++) cout<<" X"<<i+1;<<endl<<endl;(i=0;i<n;i++)
{("X%d",i+1);(j=0;j<n;j++)
{("",c[i][j]);[j][i]=c[i][j];
}("\n\n");
}(i=0;ixk;-;-;(xn==xk)
{<<"Nachalnaya I konechnaya tochki sovpadayt."<<endl;();;
}(i=0;i<n;i++)
{[i]=0;[i]=65535;
}[xn]=0;[xn]=1;=xn;(xn+1,s,10);(i=1;i<=n;i++)
{(path[i],"X");(path[i],s);
}
{(i=0;i<n;i++)((c[p][i]!=65535)&&(!flag[i])&&(i!=p))
{(l[i]>l[p]+c[p][i])
{(i+1,s,10);(path[i+1],path[p+1]);(path[i+1],"-X");(path[i+1],s);
}[i]=minim(l[i],l[p]+c[p][i]);
}=min(n);[p]=1;
}(p!=xk);(l[p]!=65535)
{<<"Put: "<<path[p+1]<<endl;<<"Dlina puti: "<<l[p]<<endl;
}<<"takogo puti ne syshestvuet!"<<endl;
getch();
}