VPF::Обход матрицы - Форум программистов

wwwdiz

Дата 28.11.2006, 13:14 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 89
Регистрация: 13.4.2006

Репутация: нет
Всего: 1

Дана матрица:

Код


int mass[9][9]={0,  15, 35, 100, 40, 25, 15, 20, 0,
           15,   0,  0, 120,  0,  0,  0,  0, 0,
           35,   0,  0,   0,  0,  0,  0,  0, 0,
          100, 120,  0,   0,  0,  0,  0,  0, 0,
           40,   0,  0,   0,  0, 50,  0,  0, 0,
           25,   0,  0,   0, 50,  0, 25,  0, 0,
           15,   0,  0,   0,  0, 25,  0, 15, 35,
           20,   0,  0,   0,  0,  0, 15,  0, 35,
        0,   0,  0,   0,  0,  0, 35, 35,  0};

Матрица mass[j][i] описывает вершину j и её связь с вершиной i
Если i=0 то связи нет....
Так вот надо вычислить через какие вершины прийдётся пройти чтобы из вершины А попасть в вершину j....

Вот мой код:

Код


int fir, sec, l,z, d;
void find()
{
    printf("Vvedite nomer verchini A:");
    scanf("%d", &fir);
    printf("Vvedite nomer verchini B:");
    scanf("%d", &sec);
  z=sec-1;
  int uk7[10];   // массив куда будут записываться нужные  вершины
  i=0;  bol=0;

 for  (l=8; l>=0;  l--)
    {  
             for(d=sec-1; d>=fir-1; d--)
        {
            
            if (mass[l][d]!=0&&d==z)
                              {
                                z=z-1;
                                bol=1; 
               }
            
        };

        if (bol==1) {uk7[i]=l+1; i++;}
        bol=0;
    
    };

 for(j=0;j<i;j++){ printf("%d_", uk7[j]);     };
}
main()
{
 find();
 getch();
}

Результат таков что он захватывает одну лишнюю вершину например если A=1 B=9
Народ HELP!!!!!!!!! smile

JackYF

Дата 28.11.2006, 16:11 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Посмотри на algolist.manual.ru.
В разделе алгоритмы на графах, поиск кратчайшего пути.

И там все написано... и исходники тоже есть.

--------------------

Пожаловаться на меня как модератора можно здесь.

darkness

Дата 30.11.2006, 11:10 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 173
Регистрация: 5.8.2006
Где: Москва

Репутация: нет
Всего: 1

wwwdiz, просмотрел я твой алгоритм там и рядом не лежит поиск кратчайшего пути, но сам поиск есть. Посидел немного, повтыкал, вот что у меня получилось:

Код


printf("Vvedite nomer verchini A:");
    scanf("%d", &fir);
    printf("Vvedite nomer verchini B:");
    scanf("%d", &sec);

      if (fir>sec) { l=sec; sec=fir; fir=l;}

    int uk8[10];
    z=sec-1;
   int uk7[10];
   j=0;

   for(i=fir; i<sec; i++) if(mass[z][i-1]==0) j++;


//if(j==sec-fir){ uk7[0]=sec-1; i=1;/*printf("sdf");*/} else i=0;

// if( uk7[i-1]!=fir-1) {uk7[i]=fir-1; i++;}


   bol=0;
   l1=0;
   for  (l=8; l>=0;  l--)
    {
     for(d=sec-1; d>=fir-1; d--)
       {
          if (mass[l][d]!=0&&d==z&&mass[l-1][d-1]==0)        // вот здесь ты не поставил  
//ещё одно условие без него и записывются лишние вершины из матрицы
          {
           z=z-1; bol=1; uk1[l]->ob=1;
          }
       };

    if (bol==1) {uk7[i]=l;i++; }
    bol=0;
    };

 if(uk7[0]!=sec-1) { for(j=0; j<i; j++) uk8[j]=uk7[j]; uk7[0]=sec-1;
             for(j=1; j<=i; j++) uk7[j]=uk8[j-1]; i++; }


 if( uk7[i-1]!=fir-1) {uk7[i]=fir-1; i++;}  //всё массив этот содержит все нужные вершины,
//включая fir и sec

--------------------

Вина каких стран Вы предпочитаете в это время суток? (Булгаков. "Мастер и Маргарита")

comp

Дата 30.11.2006, 18:47 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 61
Регистрация: 15.11.2006

Репутация: нет
Всего: 1

Заметьте, нужен любой путь.

Код


int dfs(int v1, int v2)
{
  if (v1 == v2) return 1;

  mark[v1] = 1;
  for (int i = 0; i < n; i++)
  {
    if (!mark[i] && YourMatr[v1][i])
    {
      if (dfs(i, v2))
         {
           printf("%d", i);
           return 1;
         }
    }
  }

 mark[v1] = 0;
 return 0;
}

YourMatr - матрица смежности.
mark - были ли мы в i-й вершине, или нет. массив флагов.
Ну и твой путь выведеться с конца, если он существует.

Это сообщение отредактировал(а) comp - 30.11.2006, 18:47

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »