Дан неориентированный граф. Вершинам прописаны веса. Определить путь минимального веса между двумя заданными вершинами графа, причем по каждой дуге разрешается пройти только один раз.
Код:
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#define max 10
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
int v,e,A[max][max],B[max];
int MinP[max],m;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{St1->Cells[0][0]="Nr";
St1->Cells[1][0]="V1";
St1->Cells[2][0]="V2";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
v=StrToInt(Edit1->Text);
e=StrToInt(Edit2->Text);
St1->RowCount=e+1;
for(int i=1;i<=e;i++)
St1->Cells[0][i]=i;
Label1->Visible=true;
St1->Visible=true;
Button2->Visible=true;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{for(int i=1;i<=e;i++)
{A[StrToInt(St1->Cells[1][i])-1][StrToInt(St1->Cells[2][i])-1]=1;
A[StrToInt(St1->Cells[2][i])-1][StrToInt(St1->Cells[1][i])-1]=1;}
Label2->Visible=true;
St2->Visible=true;
Button3->Visible=true;
St2->RowCount=v;
for(int j=0;j<=v;j++)
St2->Cells[0][j]=j+1;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button3Click(TObject *Sender)
{for(int i=0;i<v;i++)
B[i]=StrToInt(St2->Cells[1][i]);
Label5->Visible=true;
Label6->Visible=true;
Edit3->Visible=true;
Edit4->Visible=true;
Button4->Visible=true;
}
//---------------------------------------------------------------------------
int push ( int a,int yk ,int g[])
{
yk+=1;
g[yk]=a;
return yk;
}
//---------------------------------------------------------------------------
int pop ( int *a,int yk,int g[])
{
*a=g[yk];
yk-=1;
return yk;
}
//---------------------------------------------------------------------------
int f_s ( int yk, int g[])
{ int r=g[yk];
return r;
}
//---------------------------------------------------------------------------
int p1(int sm[][max],int i,int n)
{int j=-1;
for(int t=0;t<n;t++)
if(sm[i][t]==1 )
{j=t;
t=n;
}
return j;
}
//------------------------------------------------------------------------
int p_m(int vs,int k,int u,int s[],int*minv,int pm[])
{ int r,i;
if(k==1)
{*minv=vs;
r=0;
for(i=u;i>-1;i--,r++)
pm[r]=s[i];
}
else
if(vs<*minv)
{*minv=vs;
r=0;
for(i=u;i>-1;i--,r++)
pm[r]=s[i];
}
return r;
}
//---------------------------------------------------------------------------
bool povt(int u,int s[],int p)
{bool f=true;
for(int i=u;i>-1;i--)
if(s[i]==p)
f=false;
return f;
}
//---------------------------------------------------------------------------
void vivod(int m,int MinP[],TStringGrid *St3)
{ for(int i=m-1;i>-1;i--)
St3->Cells[m-1-i][0]=MinP[i];
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button4Click(TObject *Sender)
{Label7->Visible=true;
Label8->Visible=true;
Edit5->Visible=true;
St3->Visible=true;
int v1=StrToInt(Edit3->Text);
int v2=StrToInt(Edit4->Text);
if ((v1>v)||(v2>v))
ShowMessage("Таких вершин не существует");
else
{ bool pr;
int minves,j;
int k=0;
int u=-1,s[max];
int i=v1-1;
u=push(i+1,u,s);
int ves=B[v1-1];
do
{
do
{ j=p1(A,i,v);
if(j>-1)
{ if( povt(u,s,j+1))
{
ves+=B[j];
A[i][j]=0;
A[j][i]=0;
u=push(j+1,u,s);
i=j;
}
else
A[i][j]=0;
};
}
while ((j!=v2-1)&&j!=-1);
if (j==v2-1)
{
k++;
pr=true;
m=p_m(ves,k,u,s,&minves,MinP);
u=pop(&i,u,s);
ves-=B[j];
i=f_s(u,s)-1;
}
else
{
if(i!=v1-1)
{ pr=true;
ves-=B[i];
u=pop(&i,u,s);
i=f_s(u,s)-1;
}
else pr=false;
}
}while (pr);
St3->Visible=true;
St3->ColCount=m;
if (m>0)
{
vivod(m,MinP,St3);
Edit5->Text=IntToStr(minves);
}
else
ShowMessage("Путь между вершинами "+IntToStr(v1)+ " и " +IntToStr(v2) +" отсутствует");
}
}
//---------------------------------------------------------------------------
и,если можно, функциональные тесты