Алгоритм Прима, нахождение МОД Опции

[Andrewshkovskii]

Давно не виделись..всем привет! вот код неправильно работающего алгоритма Прима ( http://www.software.unn.ac.ru/cluster/cgi-...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);

[Andrewshkovskii]

Я тут сейчас сравнивал значения, и наткнулся на ошибку(или это не в этом алгоритме ошибка..) в общем, опять же , с того же сайта моего однокурсника МОД получается не такой, при 19 значениях и параметр "Транзит без переработки" , в строке Курган X Егоршино, стоит 134, а в нашем случае там 0 , и 92 на Курган х Омск, хотя остов получается нормальным, но при кластеризации по тем же самым параметрам появляются 2 одинаковых кластера
Вот исходные данные матрицы...
Размер 19

{ 0,177,171,642,981,15,403,1315,689,1119,311,1201,420,1103,595,930,89,311,1020},
{ 177,0,348,465,804,192,226,1138,866,942,134,1024,243,926,772,753,88,134,1197},
{ 171,348,0,813,1152,156,574,1486,518,1290,482,1372,591,1274,424,1101,260,482,849}
,
{ 642,465,813,0,339,657,239,673,1331,477,331,559,222,461,1237,288,553,331,1662},
{ 981,804,1152,339,0,996,578,334,1670,138,670,220,561,122,1576,51,892,670,2001},
{ 15,192,156,657,996,0,418,1330,674,1134,326,1216,435,1118,580,945,104,326,1005},
{ 403,226,574,239,578,418,0,912,1092,716,92,798,17,700,998,527,314,92,1423},
{ 1315,1138,1486,673,334,1330,912,0,2004,196,1004,114,895,212,1910,385,1226,1004,2
335},
{ 689,866,518,1331,1670,674,1092,2004,0,1808,1000,1890,1109,1792,94,1619,778,1000,
331},
{ 1119,942,1290,477,138,1134,716,196,1808,0,808,82,699,16,1714,189,1030,808,2139},

{ 311,134,482,331,670,326,92,1004,1000,808,0,890,109,792,906,619,222,0,1331},
{ 1201,1024,1372,559,220,1216,798,114,1890,82,890,0,781,98,1796,271,1112,890,2221}
,
{ 420,243,591,222,561,435,17,895,1109,699,109,781,0,683,1015,510,331,109,1440},
{ 1103,926,1274,461,122,1118,700,212,1792,16,792,98,683,0,1698,173,1014,792,2123},

{ 595,772,424,1237,1576,580,998,1910,94,1714,906,1796,1015,1698,0,1525,684,906,425
},
{ 930,753,1101,288,51,945,527,385,1619,189,619,271,510,173,1525,0,841,619,1950},
{ 89,88,260,553,892,104,314,1226,778,1030,222,1112,331,1014,684,841,0,222,1109},
{ 311,134,482,331,670,326,92,1004,1000,808,0,890,109,792,906,619,222,0,1331},
{ 1020,1197,849,1662,2001,1005,1423,2335,331,2139,1331,2221,1440,2123,425,1950,110
9,1331,0}

А вот и остов :

{0,0,0,0,0,15,0,0,0,0,0,0,0,0,0,0,89,0,0},
{0,0,0,0,0,0,0,0,0,0,134,0,0,0,0,0,88,0,0},
{0,0,0,0,0,156,0,0,0,0,0,0,0,0,424,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,222,0,0,288,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,122,0,51,0,0,0},
{15,0,156,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,92,0,17,0,0,0,0,92,0},
{0,0,0,0,0,0,0,0,0,0,0,114,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,94,0,0,0,331},
{0,0,0,0,0,0,0,0,0,0,0,82,0,16,0,0,0,0,0},
{0,134,0,0,0,0,92,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,114,0,82,0,0,0,0,0,0,0,0,0},
{0,0,0,222,0,0,17,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,122,0,0,0,0,16,0,0,0,0,0,0,0,0,0},
{0,0,424,0,0,0,0,0,94,0,0,0,0,0,0,0,0,0,0},
{0,0,0,288,51,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{89,88,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,92,0,0,0,0,0,0,0,0,0,0,0,0}, << вот здесь
{0,0,0,0,0,0,0,0,331,0,0,0,0,0,0,0,0,0,0}

А вот

Сообщение отредактировано: Andrewshkovskii - 25.11.2009 15:07