Давно не виделись..всем привет! вот код неправильно работающего алгоритма Прима ( http://www.software.unn.ac.ru/cluster/cgi-bin/index.cgi?id=101&work=10&topic=1 ). Помогите найти ошибку, он не правильно считает минимальное остовное дерево (мод http://ru.wikipedia.org/wiki/Остовное_дерево ).
Код строго на с++. МОД необходимо представлять ввиде матрицы.
Уже не знаю что делать, глаза ошибки не могут найти..
int dm[matrixSize][matrixSize];//матрица смежности графа
int sm[matrixSize][matrixSize];//матрица МОД
int used[matrixSize];//использованные вершины
int count=0;
int min ;
for (int i=0; i< matrixSize; ++i)
{
used[i]=0;
for(int j=0;j< matrixSize;++j)
sm[i][j]=0;
}
used[0]=1;
do {
min=std::numeric_limits<int>::max();
for(int i=0;i<matrixSize;++i)
{
if (used[i]!=0)
{
for(int j=0;j<matrixSize;++j)
if ( (dm[j][i] < min) && (dm[j][i]!=0) && (used[j])==0)
min=dm[j][i];
}
}
for(int i=0;i < matrixSize;++i)
for(int j=0;j<matrixSize;++j)
if( (dm[j][i]== min) && (used[j]==0))
{
used[j] =1;
sm[j][i]= sm[i][j] = min;
count++;
i=matrixSize;
break;
}
}while(count < matrixSize-1);
const int matrixSize = 6;Вот чего выдает твой код:
int dm[matrixSize][matrixSize] =
{
{ 0, 6, 1, 5, 0, 0 },
{ 6, 0, 5, 0, 3, 0 },
{ 1, 5, 0, 5, 6, 4 },
{ 5, 0, 5, 0, 0, 2 },
{ 0, 3, 6, 0, 0, 6 },
{ 0, 0, 4, 2, 6, 0 }
}; // матрица смежности графа из Ахо/Хопкрофта/Ульмана, стр. 211
// ...
// выводим полученную матрицу:
for(int i = 0; i < matrixSize; i++)
{
for(int j = 0; j < matrixSize; j++)
{
std::cout << sm[i][j] << " ";
}
std::cout << std::endl;
}
0 0 1 0 0 0
0 0 5 0 3 0
1 5 0 0 0 4
0 0 0 0 0 2
0 3 0 0 0 0
0 0 4 2 0 0
Для большой матрицы(17х17), вот такой вот :
0 , 465 , 2545 , 396 , 1465 , 1320 , 281 , 676 , 776 , 2652 , 438 , 2385 , 134 , 2553 , 295 , 869 , 2486
465 , 0 , 2080 , 69 , 1000 , 855 , 184 , 1141 , 311 , 2187 , 27 , 1920 , 331 , 2088 , 170 , 404 , 2021
2545 , 2080 , 0 , 2149 , 1080 , 1225 , 2264 , 3221 , 1769 , 107 , 2107 , 160 , 2411 , 8 , 2250 , 1676 , 59
396 , 69 , 2149 , 0 , 1069 , 924 , 115 , 1072 , 380 , 2256 , 42 , 1989 , 262 , 2157 , 101 , 473 , 2090
1465 , 1000 , 1080 , 1069 , 0 , 145 , 1184 , 2141 , 689 , 1187 , 1027 , 920 , 1331 , 1088 , 1170 , 596 , 1021
1320 , 855 , 1225 , 924 , 145 , 0 , 1039 , 1996 , 544 , 1332 , 882 , 1065 , 1186 , 1233 , 1025 , 451 , 1166
281 , 184 , 2264 , 115 , 1184 , 1039 , 0 , 957 , 495 , 2371 , 157 , 2104 , 147 , 2272 , 14 , 588 , 2205
676 , 1141 , 3221 , 1072 , 2141 , 1996 , 957 , 0 , 1452 , 3328 , 1114 , 3061 , 810 , 3229 , 971 , 1545 , 3162
776 , 311 , 1769 , 380 , 689 , 544 , 495 , 1452 , 0 , 1876 , 338 , 1609 , 642 , 1777 , 481 , 93 , 1710
2652 , 2187 , 107 , 2256 , 1187 , 1332 , 2371 , 3328 , 1876 , 0 , 2214 , 267 , 2518 , 99 , 2357 , 1783 , 166
438 , 27 , 2107 , 42 , 1027 , 882 , 157 , 1114 , 338 , 2214 , 0 , 1947 , 304 , 2115 , 143 , 431 , 2048
2385 , 1920 , 160 , 1989 , 920 , 1065 , 2104 , 3061 , 1609 , 267 , 1947 , 0 , 2251 , 168 , 2090 , 1516 , 101
134 , 331 , 2411 , 262 , 1331 , 1186 , 147 , 810 , 642 , 2518 , 304 , 2251 , 0 , 2419 , 161 , 735 , 2352
2553 , 2088 , 8 , 2157 , 1088 , 1233 , 2272 , 3229 , 1777 , 99 , 2115 , 168 , 2419 , 0 , 2258 , 1684 , 67
295 , 170 , 2250 , 101 , 1170 , 1025 , 14 , 971 , 481 , 2357 , 143 , 2090 , 161 , 2258 , 0 , 574 , 2191
869 , 404 , 1676 , 473 , 596 , 451 , 588 , 1545 , 93 , 1783 , 431 , 1516 , 735 , 1684 , 574 , 0 , 1617
2486 , 2021 , 59 , 2090 , 1021 , 1166 , 2205 , 3162 , 1710 , 166 , 2048 , 101 , 2352 , 67 , 2191 , 1617 , 0
0 , 0 , 0 , 0 , 0 , 0 , 0 , 676 , 0 , 0 , 0 , 0 , 134 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 311 , 0 , 27 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 8 , 0 , 0 , 59 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 42 , 0 , 0 , 0 , 101 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 145 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 145 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 451 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 147 , 0 , 14 , 0 , 0 ,
676 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 311 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 93 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 99 , 0 , 0 , 0 ,
0 , 27 , 0 , 42 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 101 ,
134 , 0 , 0 , 0 , 0 , 0 , 147 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 8 , 0 , 0 , 0 , 0 , 0 , 0 , 99 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 101 , 0 , 0 , 14 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 451 , 0 , 0 , 93 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 59 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 101 , 0 , 0 , 0 , 0 , 0 ,
Ну смотри, я ребра вот так нашел:
из аргыз->каменск-уральский->орехово-юдино->смычка. И все ни смыча, ни агрыз не связаны с ост вершинами..
Второй цикл, надо бы условие добавить:
for(int i=0;i < matrixSize;++i)
for(int j=0;j<matrixSize;++j)
if( (dm[j][ i ]== min) && (used[j]==0) && (used[ i ] == 1)) {
used[j] =1;
sm[j][ i ]= sm[ i ][j] = min;
count++;
i=matrixSize;
break;
}
for(int i=0;i < matrixSize;++i)
for(int j=0;j<matrixSize;++j)
if( (dm[j][ i ]== min) && (used[j]==0) && (used[ i ] == 1)) {
used[j] =1;
sm[j][ i ]= sm[ i ][j] = min;
count++;
i=matrixSize;
break;
}
Я тут сейчас сравнивал значения, и наткнулся на ошибку(или это не в этом алгоритме ошибка..) в общем, опять же , с того же сайта моего однокурсника МОД получается не такой, при 19 значениях и параметр "Транзит без переработки" , в строке Курган X Егоршино, стоит 134, а в нашем случае там 0 , и 92 на Курган х Омск, хотя остов получается нормальным, но при кластеризации по тем же самым параметрам появляются 2 одинаковых кластера
Вот исходные данные матрицы...
Размер 19
Весомые доводы.Я понял! буду пытаться придумать нормальный алгоритм.. (как же мне надоела эта задача.. )