#include <vcl.h>

#pragma hdrstop

#include «Unit1.h»

#include <vector>

#include <math.h>

using namespace std;

 // -

#pragma package (smart_init)

#pragma resource «*.dfm»

int col = 0;

struct point {

int x, y;

int number;

};

struct rib {

int x1, x2;

bool k;

};

bool fr = false;

int xr, yr, ir;

vector<point> points;

vector<rib> ribs;

TForm1 *Form1;

 // -

__fastcall TForm1:TForm1 (TComponent* Owner)

: TForm(Owner)

{

}

 // -

 // Функция для рисования линии со стрелкой

void DrawLine (TCanvas* Canvas, double x0, double y0, double x1, double y1, double ArrowAngle, int ArrowLen) {

ArrowAngle = ArrowAngle*M_PI/180;

 // Длина основной линии

int Len = sqrt((x0-x1)*(x0-x1) + (y0-y1)*(y0-y1));

 // Угол наклона основной линии

double Angle;

if (x0==x1 && y0<y1) {

Angle = M_PI/2;

}

else if (x0==x1 && y0>y1) {

Angle = 3*M_PI/2;

}

else if (x0>x1 && y0==y1) {

Angle = 0;

}

else if (x0<x1 && y0==y1) {

Angle = M_PI;

}

else if (x0>x1 && y0<y1) {

Angle = asin((y1-y0)/Len);

}

else if (x0<x1 && y0<y1) {

Angle = M_PI - asin((y1-y0)/Len);

}

else if (x0<x1 && y0>y1) {

Angle = M_PI-asin((y1-y0)/Len);

}

else if (x0>x1 && y0>y1) {

Angle = 2*M_PI+asin((y1-y0)/Len);

}

int x2 = x1 + ArrowLen * cos (Angle+ArrowAngle); // конец первого лепестка по X

int y2 = y1 - ArrowLen * sin (Angle+ArrowAngle); // конец первого лепестка по Y

int x3 = x1 + ArrowLen * cos (Angle-ArrowAngle); // конец второго лепестка по X

int y3 = y1 - ArrowLen * sin (Angle-ArrowAngle); // конец конец второго лепестка по Y

 // рисуем саму линию

Canvas->MoveTo (x0, y0);

Canvas->LineTo (x1, y1);

 // Рисуем лепестки

TPoint points[3];

points[0] = Point (x1, y1);

points[1] = Point (x2, y2);

points[2] = Point (x3, y3);

Canvas->Polygon (points, 2);

}

int res = 0;

void __fastcall TForm1: Image1MouseDown (TObject *Sender,

TMouseButton Button, TShiftState Shift, int X, int Y)

{

if (res==0) {

this->Image1->Canvas->Pen->Color=RGB (2, 0, 0);

point el;

el.x = X;

el.y = Y;

el.number = col;

points.push_back(el);

this->Image1->Canvas->Ellipse (X-10, Y-10, X+10, Y+10);

this->Image1->Canvas->TextOutA (X+10, Y, IntToStr(col));

this->Image1->Canvas->MoveTo (X, Y);

this->StringGrid1->RowCount = col+2;

this->StringGrid1->ColCount = col+2;

this->StringGrid1->Cells [col+1] [0] = IntToStr(col);

this->StringGrid1->Cells[0] [col+1] = IntToStr(col);

for (int i=1; i<this->StringGrid1->ColCount; i++) {

this->StringGrid1->Cells[i] [col+1] = «0»;

this->StringGrid1->Cells [col+1] [i] = «0»;

}

col++;

}

if (res==1) { // если не используем матрицу смежности

this->Image1->Canvas->Pen->Color=RGB (208, 20, 201);

bool f = false;

for (int i=0; i<col; i++) {

int x= point (points[i]).x;

if ((point (points[i]).x>(X-10))&&(point (points[i]).x<(X+10))&&(point (points[i]).y>(Y-10))&&(point (points[i]).y<(Y+10))) {

if (! fr) {f=true; ir =i; fr=true; this->Image1->Canvas->MoveTo (point(points[i]).x, point (points[i]).y);}

else {

DrawLine (this->Image1->Canvas, point (points[ir]).x, point (points[ir]).y, point (points[i]).x, point (points[i]).y, 10,20);

this->StringGrid1->Cells [i+1] [ir+1] = «1»;

fr=false;

}

}

}

fr=f;

}

}

 // -

void __fastcall TForm1: BitBtn1Click (TObject *Sender)

{

res=0;

}

 // -

void __fastcall TForm1: BitBtn2Click (TObject *Sender)

{

res=1;

}

 // -

void __fastcall TForm1: BitBtn3Click (TObject *Sender)

{

points.clear();

ribs.clear();

col=0;

Image1->Canvas->FillRect (Image1->Canvas->ClipRect);

this->StringGrid1->ColCount = 1;

this->StringGrid1->RowCount = 1;

this->Memo1->Lines->Clear();

}

 // -

void __fastcall TForm1: StringGrid1EndDock (TObject *Sender,

TObject *Target, int X, int Y)

{

int k=0;

}

 // -

void __fastcall TForm1: StringGrid1SetEditText (TObject *Sender, int ACol,

int ARow, const AnsiString Value)

{

if (! StringGrid1->EditorMode) {

this->Image1->Canvas->Pen->Color=RGB (208, 20, 201);

DrawLine (this->Image1->Canvas, point (points[ARow-1]).x, point (points[ARow-1]).y, point (points[ACol-1]).x, point (points[ACol-1]).y, 10,20);

}

}

struct el {

int v;

};

 // -

void __fastcall TForm1: Button2Click (TObject *Sender)

{

int n =this->StringGrid1->ColCount-1; // Количество вершин в графе

float **a; // Матрица смежности графа

a=new float *[n];

for (int i=0; i<n; i++)

a[i]=new float [n];

 // инициализация

for (int i=1; i<this->StringGrid1->ColCount; i++) {

for (int j=1; j<this->StringGrid1->ColCount; j++) {

a [i-1] [j-1] = StrToFloat (this->StringGrid1->Cells[j] [i]);

}

}

int infinity=10000; // Бесконечность

el * put;

put= new el [n];

int sumDl =10000;

int punkt=-1;

for (int versh=0; versh<n; versh++) {

int sumB = 0;

for (int kversh=0; kversh<n; kversh++) {

if (kversh!=versh) {

int s=versh; // Номер исходной вершины

int g=kversh; // Номер конечной вершины

int * x; // Массив, содержащий единицы и нули для каждой вершины,

 // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,

 // x[i]=1 - кратчайший путь в i-ю вершину уже найден

x = new int [n];

int *t; //t[i] - длина кратчайшего пути от вершины s в i

t = new int [n];

el * h; //h[i] - вершина, предшествующая i-й вершине

 // на кратчайшем пути

h = new el [n];

 //int * tr; // транспорт. 1-жд, 0-шоссе

 //tr = new int [n];

 // Инициализируем начальные значения массивов

int u; // Счетчик вершин

for (u=0; u<n; u++)

{

t[u]=infinity; // Сначала все кратчайшие пути из s в i

 // равны бесконечности

x[u]=0; // и нет кратчайшего пути ни для одной вершины

}

int v;

h[s].v=0; // s - начало пути, поэтому этой вершине ничего не предшествует

t[s]=0; // Кратчайший путь из s в s равен 0

x[s]=1; // Для вершины s найден кратчайший путь

v=s; // Делаем s текущей вершиной

while(1)

{

 // Перебираем все вершины, смежные v, и ищем для них кратчайший путь

for (u=0; u<n; u++)

{

if (a[v] [u]==0) continue; // Вершины u и v несмежные

if (x[u]==0 && t[u]>t[v]+a[v] [u]) // Если для вершины u еще не

 // найден кратчайший путь

 // и новый путь в u короче чем

 // старый, то

{

t[u]=t[v]+a[v] [u]; // запоминаем более короткую длину пути в

 // массив t и

h[u].v=v; // запоминаем, что v->u часть кратчайшего

 // пути из s->u

}

}

 // Ищем из всех длин некратчайших путей самый короткий

int w=infinity; // Для поиска самого короткого пути

v=-1; // В конце поиска v - вершина, в которую будет

 // найден новый кратчайший путь. Она станет

 // текущей вершиной

for (u=0; u<n; u++) // Перебираем все вершины.

{

if (x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший

 // путь и если длина пути в вершину u меньше

 // уже найденной, то

{

v=u; // текущей вершиной становится u-я вершина

w=t[u];

}

}

if (v==-1)

{

sumB+=infinity;

 //Memo1->Lines->Add («Нет пути из вершины»);

break;

}

if (v==g && t[g]<100) // Найден кратчайший путь,

{ // выводим его

sumB+= t[g];

break;

}

x[v]=1;

}

}

}

if (sumDl>sumB) {

punkt = versh;

sumDl = sumB;

}

}

if (punkt!=-1) {

Memo1->Lines->Add («Это пункт «+IntToStr(punkt));

Memo1->Lines->Add (» - Выводим маршруты -»);

 // теперь высчитывем маршруты до каждого пункта и выводим их

for (int versh=0; versh<n; versh++) {

if (punkt!=versh) {

int s=punkt; // Номер исходной вершины

int g=versh; // Номер конечной вершины

int * x; // Массив, содержащий единицы и нули для каждой вершины,

 // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,

 // x[i]=1 - кратчайший путь в i-ю вершину уже найден

x = new int [n];

int *t; //t[i] - длина кратчайшего пути от вершины s в i

t = new int [n];

el * h; //h[i] - вершина, предшествующая i-й вершине

 // на кратчайшем пути

h = new el [n];

 // Инициализируем начальные значения массивов

int u; // Счетчик вершин

for (u=0; u<n; u++)

{

t[u]=infinity; // Сначала все кратчайшие пути из s в i

 // равны бесконечности

x[u]=0; // и нет кратчайшего пути ни для одной вершины

}

int v;

h[s].v=0; // s - начало пути, поэтому этой вершине ничего не предшествует

t[s]=0; // Кратчайший путь из s в s равен 0

x[s]=1; // Для вершины s найден кратчайший путь

v=s; // Делаем s текущей вершиной

while(1)

{

 // Перебираем все вершины, смежные v, и ищем для них кратчайший путь

for (u=0; u<n; u++)

{

if (a[v] [u]==0) continue; // Вершины u и v несмежные

if (x[u]==0 && t[u]>t[v]+a[v] [u]) // Если для вершины u еще не

 // найден кратчайший путь

 // и новый путь в u короче чем

 // старый, то

{

t[u]=t[v]+a[v] [u]; // запоминаем более короткую длину пути в

 // массив t и

h[u].v=v; // запоминаем, что v->u часть кратчайшего

 // пути из s->u

}

}

 // Ищем из всех длин некратчайших путей самый короткий

int w=infinity; // Для поиска самого короткого пути

v=-1; // В конце поиска v - вершина, в которую будет

 // найден новый кратчайший путь. Она станет

 // текущей вершиной

for (u=0; u<n; u++) // Перебираем все вершины.

{

if (x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший

 // путь и если длина пути в вершину u меньше

 // уже найденной, то

{

v=u; // текущей вершиной становится u-я вершина

w=t[u];

}

}

if (v==-1)

{

Memo1->Lines->Add («Нет пути из вершины»);

break;

}

if (v==g) // Найден кратчайший путь,

{ // выводим его

Memo1->Lines->Add («Путь с минимальной величиной из вершины «+IntToStr(s)+» в вершину «+IntToStr(g)+» (в обратном порядке)»);

u=g;

this->Image1->Canvas->Pen->Color=RGB (0, 0, 255);

int k=0;

while (u!=s)

{

k++;

this->Memo1->Lines->Add (IntToStr(u));

this->Image1->Canvas->Pen->Color=RGB (208, 158, 20);

DrawLine (this->Image1->Canvas, point (points[h[u].v]).x, point (points[h[u].v]).y, point (points[u]).x, point (points[u]).y, 10,20);

u=h[u].v;

}

this->Memo1->Lines->Add (IntToStr(u));

this->Memo1->Lines->Add («Длина пути = «+IntToStr (t[g]));

break;

}

x[v]=1;

}}

}

}

else

{

Memo1->Lines->Add («Нет такого пункта. Возможно не все пункты соединены»);

}

}

 // -

void __fastcall TForm1: Button1Click (TObject *Sender)

{

Image1->Canvas->FillRect (Image1->Canvas->ClipRect);

this->Image1->Canvas->Pen->Color=RGB (2, 0, 0);

for (int i=0; i<col; i++) {

int X = point (points[i]).x;

int Y = point (points[i]).y;

this->Image1->Canvas->Ellipse (X-10, Y-10, X+10, Y+10);

this->Image1->Canvas->TextOutA (X+10, Y, IntToStr(i));

this->Image1->Canvas->MoveTo (X, Y);

}

this->Image1->Canvas->Pen->Color=RGB (208, 20, 201);

for (int i=1; i<this->StringGrid1->ColCount; i++) {

for (int j=1; j<this->StringGrid1->ColCount; j++) {

if (this->StringGrid1->Cells[j] [i]!= «0»)

DrawLine (this->Image1->Canvas, point (points[i-1]).x, point (points[i-1]).y, point (points[j-1]).x, point (points[j-1]).y, 10,20);

}

}

}

 // -

void __fastcall TForm1: Button3Click (TObject *Sender)

{

res=1;

}

 // -

Размещено на Allbest.ru