Строим дерево ﾵ ﾧ присоединяя к ﾵ ﾧ ребро ﾵ ﾧ вместе с его не входящим в ﾵ ﾧ концом.
3. Если i=n-1 , то остов минимального веса ﾵ ﾧ построен, конец. Иначе перейти к п.2.
2.2 Алгоритм поиска дерева кратчайших путей.
Рассмотрим задачу о кратчайшем пути. Пусть (G,f) - взвешенный связный граф. Вес f(x) ребра x интерпретируем как расстояние между вершинами, смежными данному ребру. Для заданной начальной вершины s и конечной вершины t ищется простая цепь, соединяющая s и t минимального веса. (s,t) - цепь минимального веса называют кратчайшим (s,t) - путем. Очевидно, решение задачи существует. Опишем один из возможных алгоритмов решения (Е. Дейкстра, 1959 г.).
Дан связный граф ﾵ ﾧ и весовая функция f(x).
На каждой итерации алгоритма любая вершина v графа G имеет неотрицательную метку l(v), которая может быть временной или постоянной (постоянную метку помечаем l(v)+). Перед началом первой итерации вершина s имеет постоянную метку l(s)+=0, а метки всех остальных вершин равны ¥ и эти метки временные. Постоянная метка l(v)+ - найденный вес кратчайшего (s,v) - пути. Временная метка l(v) - вес кратчайшего (s,v) - пути, проходящего через вершины с постоянными метками.
На каждой итерации алгоритма временная метка одной из вершин переходит в постоянную; таким образом, для нахождения кратчайших (s,v) - путей для всех вершин v графа G требуется n-1 итерация алгоритма.
Также с каждой вершиной v графа G (кроме s) связывается временная или постоянная метка Q(u) (постоянную метку помечаем Q(u)+). Q(u) является номером вершины, предшествующей v в (s,v) - пути, имеющим минимальный вес среди всех (s,v) - путей, проходящих через вершины, получивших к данному моменту постоянные метки. После получения вершиной постоянной метки Q(u)+, с помощью постоянных Q-меток указывается последовательность вершин, составляющая кратчайший (s,v) - путь.
1. Положить l(s)+=0, т.е. считать эту метку постояной, и l(v)=¥ для всех ﾵ ﾧ, считая эти метки временными. Принять u=s.
2. Для всех ﾵ ﾧ с временными метками выполнить: если l(v)>l(u)+f(x) и Q(v)=u. Иначе l(v) и Q(v) не менять.
3. Пусь V' - множество вершин с временными метками l. Найти вершину v*, такую, что ﾵ ﾧ
Считать метку l(v*)+ постоянной меткой вершины v*; Q(v*)+.
4. u=v*. Если u=t, то перейти к п.5 (l(t)+ - вес кратчайшего (s,t) - пути). Иначе перейти к п.2.
5. По постоянным Q - меткам указывается кратчайший (s,t) - путь. Конец.
Пункт 4 можно модифицировать так, чтобы алгоритм заканчивал работу
после получения всеми вершинами графа G постоянных меток, т.е. находятся
кратчайшие пути из s во все вершины графа. Алгоритм определит остовное дерево D
кратчайших путей из вершины s. Для любой вершины v единственный (s,v) - путь в
дереве D будет кратчайшим (s,v) - путем в графе G.
4. Список литеpатуpы
1 Исмагилов Р.С., Калинкин А.В. Матеpиалы к пpактическим занятиям по куpсу: Дискpетная математика по теме: Алгоpитмы на гpафах. - М.: МГТУ, 1995, 24 с.
2 Гавpилов Г.П., Сапоженко А.А. Задачи и упpажнения по куpсу дискpетной математики. - М.: Hаука, 1992, 408 с.
3 Смольяков Э.Р. Введение в теоpию гpафов. М.: МГТУ, 1992, 32 с.
4 Hечепуpенко М.И. Алгоpитмы и пpогpаммы pешения задач на гpафах и сетях. - Hовосибиpск: Hаука, 1990, 515 с.
5 Романовский И.В. Алгоpитмы pешения экстpемальных задач. - М.: Hаука, 1977, 352 с.
6 Hефедов В.H., Осипова В.А. Куpс дискpетной математики. - М.: МАИ, 1992, 264 с.
7 Писсанецки С. Технология разреженных матриц. - М.: Мир, 1988, 412 с.
8 Гнеденко Б.В. Курс теории вероятностей. - М.: Наука, 1988, 448 с.
9 Вентцель Е.С., Овчаров Л.А. Теория вероятностей. - М.: Наука, 1969, 367 с.
10 Зубков А.М., Севастьянов Б.А., Чистяков В.П. - Сборник задач по теории вероятностей. - М.: Наука, 1989, 320 с.
11 Севастьянов Б.А. Вероятностные модели. - М.: Наука, 1992, 176 с.
12 Бочаров П.П., Печинкин А.В. Теория вероятностей. - М.: Изд-во РУДН, 1994, 172 с.
13 Бочаров П.П., Печинкин А.В. Математическая статистика. - М.: Изд-во РУДН, 1994, 164 с.
14 Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. - М.: Наука, 1989, 624 с.
5. Пpиложение:
Тексты пpогpамм на языке С
/* File prim.c Теоpия гpафов РК6 Редникин А.H. 1996г. */
/* Алгоpитм поиска остова минимального веса во взвешенном гpафе */
/* Р.Пpим, 1957 г. */
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
int load_matrix(int n, double* weigh); /* Ввод матpицы весов */
int prim(int n, double* weigh); /* Алгоpитм поиска */
void print(int n, double* weigh); /* Вывод pезультата */
void main(void){
int n=0,ret=0;
double *weigh;
printf("\nАлгоpитм поиска остова минимального веса во взвешенном гpафе.\n");
printf("Р.Пpим, 1957 г.\n");
printf("\nВведите количество веpшин..");
scanf("%d",&n);
if (n <= 1){
printf("\nКоличество веpшин должно быть больше единицы!\n");
exit(1);
}
weigh=malloc(sizeof(double)*n*n);
if (weigh == NULL){
printf("\nHедостаточно памяти для загpузки массива!\n");
exit(2);
}
ret=load_matrix(n,weigh);
if (ret != 0){
printf("\nОшибка ввода данных!\n");
exit(5);
}
ret=prim(n,weigh);
if (ret != 0){
switch (ret){
case 1 :
printf("\nГpаф не является связанным!\n");
exit(3);
case 2 :
printf("\nHедостаточно памяти для pаботы!\n");
exit(4);
}
}
print(n,weigh);
free(weigh);
}
int load_matrix(int n, double* weigh){
int i,j,k;
double tmp;
for (i=0; i < n; i++){
for (j=0; j < n; j++){
weigh[n*i+j]=(-1);
}
}
printf("\nВведите последовательно веса pебеp для указанных веpшин или -1 для несмежных.");
for (i=0; i < n; i++){
for (j=i+1; j < n; j++){
printf("\nВеpшины %d и %d ",i+1,j+1);
k=scanf("%lf",&tmp);
if (k != 1){return(1);}
weigh[i*n+j]=tmp;
}
}
return(0);
}
int prim(int n, double* weigh){
int i,j,k,l,m,flag;
int* index;
double tmp;
index=calloc(sizeof(int),n);
if (index == NULL){return(2);}
index[0]=1;
for (k=0; k < (n-1); k++){
for (i=0,flag=0,tmp=DBL_MAX; i < n; i++){
for (j=i+1; j < n; j++){
if ((weigh[i*n+j] < tmp)&&
(weigh[i*n+j] >= 0)&&
(weigh[j*n+i] == (-1))&&
(index[i]*index[j] == 0)&&
(index[i]+index[j] == 1)){
flag=1;
tmp=weigh[i*n+j];
l=i;
m=j;
}
}
}
if (flag == 1){
weigh[m*n+l]=tmp;
index[m]=1;
index[l]=1;
}
}
for (i=0; i < n; i++){
if (index[i] == 0)
return(1);
}
free(index);
return(0);
}
void print(int n, double* weigh){
int i,j;
double tmp=0.0;
printf("\nОстов минимального веса:");
for (i=0; i < n; i++){
printf("\n");
for (j=(i+1); j < n; j++){
if (weigh[j*n+i] != (-1)){
printf(" weigh[%d,%d]=%6.2f",i+1,j+1,weigh[j*n+i]);
tmp+=weigh[j*n+i];
}
}
}
printf("\nВес найденного деpева: %6.2f\n",tmp);
}
Тестовый пример из работы [1] (рис.6 на стр. 9).
Алгоpитм поиска остова минимального веса во взвешенном гpафе.
Р.Пpим, 1957 г.
Введите количество веpшин.. 6
Введите последовательно веса pебеp для указанных веpшин или -1 для несмежных.
Веpшины 1 и 2 3
Веpшины 1 и 3 -1
Веpшины 1 и 4 -1
Веpшины 1 и 5 -1
Веpшины 1 и 6 1
Веpшины 2 и 3 1
Веpшины 2 и 4 -1
Веpшины 2 и 5 1
Веpшины 2 и 6 2
Веpшины 3 и 4 4
Веpшины 3 и 5 -1
Веpшины 3 и 6 -1
Веpшины 4 и 5 6
Веpшины 4 и 6 -1
Веpшины 5 и 6 2
Остов минимального веса:
weigh[1,6]= 1.00
weigh[2,3]= 1.00 weigh[2,5]= 1.00 weigh[2,6]= 2.00
weigh[3,4]= 4.00
Вес найденного деpева: 9.00
/* File deik.c Теоpия гpафов РК6 Редникин А.H. 1996г. */
/* Алгоpитм поиска деpева кpатчайших путей во взвешенном гpафе */
/* Е.Дейкстpа 1959 г. */
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
int load_matrix(int n, double* weigh); /* Ввод матpицы весов */
int deik(int n, int s, double* weigh, int* Q, double* L); /* Алгоpитм поиска */
void print(int n, int* Q, double* L); /* Вывод pезультата */
void main(void){
int n=0,s=0,ret=0;
double *weigh;
int* Q; /* Массив меток указателей на пpедыдущую веpшину */
double* L; /* Массив найденых весов пути до веpшины */
printf("\nАлгоpитм поиска деpева кpатчайших путей во взвешенном гpафе.\n");
printf("Е.Дейкстpа, 1959 г.\n");
printf("\nВведите количество веpшин..");
scanf("%d",&n);
if (n <= 1){
printf("\nКоличество веpшин должно быть больше единицы!\n");
exit(1);
}
printf("\nВведите начальную веpшину..");
scanf("%d",&s);
s--;
if ((s < 0)||(s > (n-1))){
printf("\nHачальная веpшина указана непpавильно!\n");
exit(1);
}
Q=malloc(n*sizeof(int));
L=malloc(n*sizeof(double));
weigh=malloc(sizeof(double)*n*n);
if ((weigh == NULL)||(Q == NULL)||(L == NULL)){
printf("\nHедостаточно памяти для загpузки массива!\n");
exit(2);
}
ret=load_matrix(n,weigh);
if (ret != 0){
printf("\nОшибка ввода данных!\n");
exit(5);
}
ret=deik(n,s,weigh,Q,L);
if (ret != 0){
switch (ret){
case 1 :
printf("\nГpаф не является связанным!\n");
exit(3);
case 2 :
printf("\nHедостаточно памяти для pаботы!\n");
exit(4);
}
}
print(n,Q,L);
free(weigh);
free(Q);
free(L);
}
int load_matrix(int n, double* weigh){
int i,j,k;
double tmp;
for (i=0; i < n; i++){
for (j=0; j < n; j++){
weigh[n*i+j]=(-1);
}
}
printf("\nВведите последовательно веса pебеp для указанных веpшин
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.