о j-тий терміну (рядок варто вводити в розгляд, якщо вона містить хоча б одну одиницю). Нехай елемент. Тоді з вершини у вершину можна потрапити за два кроки. Таким чином, можна записати. Слід зауважити, що якщо в розглянутих рядках дві або більше одиниць, то слід опрацьовувати всі можливі варіанти попадання з однієї вершини в іншу, записуючи в матрицю довжину найліпшого з них.
Лістинг програми:
# include
# include
using namespace std;
int main ()
{
int N = 0, n = 0, c = 0, i = 0, k = 0;
cout <<"----------------------------------------- ----- "<
cout <<"| Poisk optimalnogo puti v nenagrujennom orgrafe | "<
cout <<"----------------------------------------- ----- "<
case1:
cout <<"Vvedite chislo vershin v orgrafe: ";
cin>> N;
if (N <= 1)
{
cout <<"Kolichestvo vershin doljno bit '> 1! "<
goto case1;
}
///МАТРИЦЯ суміжності ::
cout <<"Zapolnite matricu smejnosti (esli puti net, vvedite 0; esli put 'est', vvedite 1): ";
float ** A = new float * [N];
for (i; i
A [i] = new float [N];
for (i = 0; i
for (int k = 0; k
{
cout <<"V";
printf ("% d", i +1);
cout <<"-> V";
printf ("% d", k +1);
cout <<'=';
scanf ("% f", & A [i] [k]);
if ((A [i] [k]! = 0) && (A [i] [k]! = 1))
{
cout <<"Vvodite tol'ko 0 ili 1! "<
return 0;
}
if ((i == k) & (A [i] [k] == 1))
{
cout <<"Na glavnoi diagonali doljni bit 'nuli! "<
return 0;
}
}
//// Звідки і куди? (Початкова і кінцева вершина в графі!!)
case2:
cout <<"Vvedite nachalnuiu vershinu: ";
cin>> n;
if (n> N)
{
cout <<"Net takoi vershini! "<
goto case2;
}
if (n == 0)
{
cout <<"Net takoi vershini! "<
goto case2;
}
case3:
cout <<"Vvedite konechnuyu vershinu: ";
cin>> c;
if (c> N)
{
cout <<"Net takoi vershini! "<
goto case3;
}
if (c == 0)
{
cout <<"Net takoi vershini! "<
goto case3;
}
///Масив, де записується число кроків
int h = 1;
float * B = new float [N];
for (i = 0; i
{
B [i] = 0;
}
// В масиві B [N-1] шукаємо вершини, які достжіми з початку шляху
// т.е за один крок
for (k = 0; k
{
if (A [n-1] [k] == 1)
B [k] = 1;
}
// Елементи фронту хвилі
while (h <50)
{
for (i = 0; i
{
for (k = 0; k
{
if ((B [i] == h) && (A [i] [k] == 1) && (B [k] == 0))
B [k] = h +1;
}
}
h + +;
}
B [n-1] = 0;
if (B [c-1]! = 0)
{
///Вивід на екран таблицю
cout <<" nTablica stoimosti minimalnogo puti: "<
for (i = 0; i
{
printf ("% f", B [i]);
}
// Пошук зворотного шляхи
cout <<" n nOptimal'nii put '(v obratnom poryadke): n "<<" V ";
printf ("% d", c);
h = c-1;
int b = B [c-1];
while (b> 0)
{
for (i = 0; i
if ((A [i] [h] == 1) && (B [i] == B [h] -1))
{
cout <<"V";
printf ("% d", i +1);
h = i;
b -;
}
}
cout <<" n";
}
else
{
cout <<" nPuti net! n";
}
delete A, B; return 0;
}
Приклади виконання програми:
1.
2.
3.
Використана література:
1. В«Теорія графівВ». Методичні вказівки по підготовці до контрольних робіт з дисципліни В«Дискретна математикаВ». Сост.: Н.І. Житнікова, Г.І. Федорова, А.К. Галімов. - Уфа, 2005 -37 с.
2. Курс лекцій з дискретній математиці Житникова В.П.
3. В«Самовчитель С + +В», Переклад з англ. -3 Изд .. - СПб.: БХВ-Петербург, 2005 - 688 с.
4. В«Дискретна математика для програмістів В», Ф.А.Новіков.
5. В«Введення в дискретну математику В», Яблонський.
6. В«Курс дискретної математики В», Нефер, Осипова.
7. В«ІнформатикаВ» Л.З.Шауцукова.
