Код:
#include <iostream>
using namespace std;
#define word unsigned int
int p;
int flag[8], l[8];
int min()
{
int i, result;
for(i=0;i<8;i++)
if(!(flag[i])) result=i;
for(i=0;i<8;i++)
if((l[result]>l[i])&&(!flag[i])) result=i;
return result;
}
word minim(word x, word y)
{
if(x<y) return x;
return y;
}
int main()
{
setlocale(LC_ALL, "Russian");
cout << "Исходный граф: " << endl;
cout << "1.__________.__________.3" << endl;
cout << " | e1 2| e2 /|" << endl;
cout << " | | / |" << endl;
cout << " | | / |" << endl;
cout << " | | / |" << endl;
cout << " |e3 e4| e5/ |e6" << endl;
cout << " | | / |" << endl;
cout << " | | / |" << endl;
cout << " | | / |" << endl;
cout << " | | / |" << endl;
cout << "4.__________./_________.6" << endl;
cout << " | e7 /5 e8 /" << endl;
cout << " | / / " << endl;
cout << " | / / " << endl;
cout << " | / / " << endl;
cout << " |e9 /e10 e11/ " << endl;
cout << " | / / " << endl;
cout << " | / / " << endl;
cout << " | / / " << endl;
cout << " | / / " << endl;
cout << "7./_________./8" << endl;
cout << " e12" << endl;
int A[12], a;
cout << "Введите веса ребер по очередности: e1, e2 и т.д. После ввода каждого числа нажимайте Enter, вводить только целочисленные значения." << endl;
for (int i = 0; i < 12; i++)
{
cin >> a;
A[i] = a;
}
cout << "Веса ребер:" << endl;
for (int i = 0; i < 12; i++)
{
cout << "e" << i + 1 << "=" << A[i];
cout << endl;
}
int P[8][12] = { {1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1} };
int C[8][8] = { {0, A[0], 0, A[2], 0, 0, 0, 0},
{A[0], 0, A[1], 0, A[3], 0, 0, 0},
{0, A[1], 0, 0, A[4], A[5], 0, 0},
{A[2], 0, 0, 0, A[6], 0, A[8], 0},
{0, A[3], A[4], A[6], 0, A[7], A[9], 0},
{0, 0, A[5], 0, A[7], 0, 0, A[10]},
{0, 0, 0, A[8], A[9], 0, 0, A[11]},
{0, 0, 0, 0, 0, A[10], A[11], 0} };
int c, d;
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
cout << C[i][j] << ' ';
cout << endl;
}
cout << "Введите вершины, между которыми нужно найти кратшайший путь:" << endl;
cin >> c >> d;
while (c < 1 || c > 8 || d < 1 || d > 8)
{
cout << "Вершин(-ы), введеных(-ой) вами, нет. Введите снова" << endl;
cin >> c >> d;
}
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
if (C[i][j] == 0) C[i][j] = 65535;
c--;
d--;
if (c == d)
{
cout << "Вершины равны, кратчайший путь равен 0" << endl;
system("pause");
return 0;
}
for (int i = 0; i < 8; i++)
{
flag[i] = 0;
l[i] = 65535;
}
l[c] = 0;
flag[c] = 1;
p = c;
int path[8] = {0}, path2[8] = {0};
path[0] = c + 1;
do
{
for(int i = 0; i < 8; i++)
if((C[p][i] != 65535)&&(!flag[i])&&(i!=p))
{
if(l[i]>l[p]+C[p][i])
{
path[i+1] = p + 1;
}
l[i]=minim(l[i],l[p]+C[p][i]);
}
p=min();
flag[p]=1;
}
while(p != d);
cout << "Путь: " << endl;
for (int i = 0; i < 8; i++)
if (path[i] != 0)
cout << path[i] << "->";
cout << d + 1;
cout<<"Длина пути: "<<l[p]<<endl;
system ("pause");
return 0;
}
Рисунок графа в коде.
Длина пути находится, но путь нет. Что не так?