Здравствуйте.
У меня проблема...мне нужно сделать , чтобы в графе искался кратчайший путь через 3 заданые вершины...
У меня он просто пока ищет просто кратчайший путь...
Unit1.cpp
| Код |
*********
...........
void __fastcall TfrmPaths::mnuPaths(TObject *Sender)
{
int v1 = atoi(txtVFrom->Text.c_str());
int v2 = atoi(txtVTo->Text.c_str());
if (v1 > mmm.Length || v2 > mmm.Length || v1 < 1 || v2 < 1 || v1 == v2) {
Application->MessageBox("Íîìåðà âåðøèí äîëæíû áûòü:\nðàçëè÷íû\níå áîëåå îáùåãî êîëè÷åñòâà âåðøèí\níå ìåíåå 1!", NULL, MB_OK);
return;
}
Depth a;
Widthh b;
TMenuItem *sndr = dynamic_cast<TMenuItem*>(Sender);
switch (sndr->Tag) {
case 1:
myPtr = &a;
myPtr->set_vfrom(v1);
myPtr->set_vto(v2);
myPtr->set_object(memoResult);
myPtr->set_matrix(&mmm);
myPtr->set_search(0);
myPtr->execute();
break;
case 2:
myPtr = &a;
myPtr->set_vfrom(v1);
myPtr->set_vto(v2);
myPtr->set_object(memoResult);
myPtr->set_matrix(&mmm);
myPtr->set_search(1);
frmProcess->ShowModal();
break;
case 3:
myPtr = &b;
myPtr->set_vfrom(v1);
myPtr->set_vto(v2);
myPtr->set_object(memoResult);
myPtr->set_matrix(&mmm);
myPtr->execute();
break;
}
}
.................
|
| Код |
#include "Width.h"
// конструктор класса
Widthh::Widthh() {
// задаем начальные начения пераметров
prv_from = 0;
prv_to = 0;
prv_total = 0;
}
// деструктор класа
Widthh::~Widthh() {
;
}
// передаем указатель на дим. массив
void Widthh::set_matrix(const DynamicArray<DynamicArray<int> > *p){
prv_mmm = p;
prv_total = p->Length;
}
// устанавливаем вершину из которой будем искать путь
void Widthh::set_vfrom(const int &p) {
prv_from = p;
}
// устанавливаем вершину в которую мы приходим
void Widthh::set_vto(const int &p) {
prv_to = p;
}
// принемаем указатель на объект для вывода данных
void Widthh::set_object(TMemo *p){
prv_obj = p;
}
// начинаем решение
void Widthh::execute() {
Widthh::i2j(*prv_mmm);
}
void Widthh::i2j(const DynamicArray<DynamicArray<int> > &matr) {
// для пройденных вершин
DynamicArray<bool > VUsed;
// для хранения пройденных вершин
DynamicArray<int > Prev, Path;
Prev.Length = prv_total;
Path.Length = prv_total;
VUsed.Length = prv_total;
for (int k=0; k < prv_total; k++) {
Path[k] = 0;
Prev[k] = 0;
VUsed[k] = false;
}
/* в переменой heaв будет находиться номер вершины из которой идет волна
при помощи переменной tail новые вершины перемещаются в path*/
int head = 1, tail = 1;
AnsiString s = "";
bool PathFinded = false;
int i = prv_from;
Path[tail-1] = i;
VUsed[i-1] = true;
while (head <= tail && !PathFinded) {
int v = Path[head-1];
head++;
for (int k = 1; k <= prv_total; k++)
if (matr[v-1][k-1] == 1 && !VUsed[k-1]) {
tail++;
Path[tail-1] = k;
VUsed[k - 1] = true;
Prev[k - 1] = v;
if (k == prv_to) {
PathFinded = true;
break;
}
}
}
if (PathFinded) {
int k = prv_to;
s = IntToStr(prv_to);
while (Prev[k - 1] != 0) {
s = IntToStr(Prev[k - 1]) + " - " + s;
k = Prev[k - 1];
}
} else
s = "Путь найден
prv_obj->Lines->Add("короткий путь поиском в ширину
prv_obj->Lines->Add(s);
prv_obj->Lines->Add("");
Prev.Length = 0;
Path.Length = 0;
VUsed.Length = 0;
}
|
Зарание благодарен. |