Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Помогите пожалуйста

77K
23 декабря 2011 года
yuriim
1 / / 22.12.2011
Доброго вам времени суток уважаемые программисты. У меня проблема вот такого рода: нужно реализовать алгоритм Дейкстры в Borland C++ Builder( сделать проект). Если что вот код рабочий:
//Алгоритм Дейкстры.поиска кратчайшего пути
#include <vcl.h>
#include <iostream.h>
#include <conio.h>
#pragma hdrstop
#pragma argsused

#define VERTEXES 6 //Число вершин в графе

int v;
int main(int argc, char* argv[])
{
clrscr();
int infinity=1000; // Бесконечность
int p= VERTEXES; // Количество вершин в графе
int a[VERTEXES][VERTEXES]={ 0,1,0,0,1,3, // Матрица смежности графа
1,0,5,0,0,1,
0,5,0,5,20,1,
0,0,5,0,3,2,
1,0,20,3,0,10,
3,1,1,2,10,0 };

// Будем искать путь из вершины s в вершину g
int s; // Номер исходной вершины
int g; // Номер конечной вершины
cout<<"Vvedit pochatkovu vershynu s: "; // Номер может изменяться от 0 до p-1
cin>>s;
cout<<"Vvedit kintzevu vershynu g: ";
cin>>g;
int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
// x=0 - еще не найден кратчайший путь в i-ю вершину,
// x=1 - кратчайший путь в i-ю вершину уже найден
int t[VERTEXES]; //t - длина кратчайшего пути от вершины s в i
int h[VERTEXES]; //h - вершина, предшествующая i-й вершине
// на кратчайшем пути

// Инициализируем начальные значения массивов
int u; // Счетчик вершин
for (u=0;u<p;u++)
{
t=infinity; //Сначала все кратчайшие пути из s в i
//равны бесконечности
x=0; // и нет кратчайшего пути ни для одной вершины
}
h=0; // s - начало пути, поэтому этой вершине ничего не предшествует
t=0; // Кратчайший путь из s в s равен 0
x=1; // Для вершины s найден кратчайший путь
v=s; // Делаем s текущей вершиной

while(1)
{
// Перебираем все вершины, смежные v, и ищем для них кратчайший путь
for(u=0;u<p;u++)
{
if(a[v]==0)continue; // Вершины u и v несмежные
if(x==0 && t>t[v]+a[v]) //Если для вершины u еще не
//найден кратчайший путь
// и новый путь в u короче чем
//старый, то
{
t=t[v]+a[v]; //запоминаем более короткую длину пути в
//массив t и
h=v; //запоминаем, что v->u часть кратчайшего
//пути из s->u
}
}

// Ищем из всех длин некратчайших путей самый короткий
int w=infinity; // Для поиска самого короткого пути
v=-1; // В конце поиска v - вершина, в которую будет
// найден новый кратчайший путь. Она станет
// текущей вершиной
for(u=0;u<p;u++) // Перебираем все вершины.
{
if(x==0 && t<w) // Если для вершины не найден кратчайший
// путь и если длина пути в вершину u меньше
// уже найденной, то
{
v=u; // текущей вершиной становится u-я вершина
w=t;
}
}
if(v==-1)
{
cout<<"Нет пути из вершины "<<s<<" в вершину "<<g<<"."<<endl;
break;
}
if(v==g) // Найден кратчайший путь,
{ // выводим его
cout<<"Naykorotshyy slah vid vershyny "<<s<<" v vershynu "<<g<<":";
u=g;
while(u!=s)
{
cout<<" "<<u;
u=h;
}
cout<<" "<<s<<". Dovzhyna shlyahu = "<<t[g];
break;
}
x[v]=1;
}
getch();
}
/*Программа запрашивает вершины s и q и выводит кратчайший путь. Например, после ввода s = 3, q = 6, программа выводит

Нет пути из вершины 3 в вершину 6.

После ввода s = 0, q = 2 программа выводит

Кратчайший путь из вершины 0 в вершину 2: 2 5 1 0. Длина пути = 3.*/
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог