Алгоритм Дейкстры рулит
| Код |
// Алгоритм Дейкстры
// нахождение наименьшего расстояяния от заданной точки
// до всех остальных
#include<iostream.h>
#include<conio.h>
#define M ( sizeof(cities)/sizeof(cities[ 0 ]) )
#define N ( sizeof(inf)/sizeof(inf[ 0 ]) )
//якобы бесконечность, данное число должно быть больше
//максимального расстояния (по правилам алгоритма)
#define INFINITY 10000
//от какой точки пляшем :)
#define dance 2
//пункты
char cities[ ][ 50 ]={ "A", "B", "C", "D", "E", "F" };
struct
{
char points[ 2 ][ 50 ]; //от пункта к пункту
int distance; //расстояние км
}inf[ ]={
{{ "A", "B" }, 65 },
{{ "B", "C" }, 40 },
{{ "C", "D" }, 60 },
{{ "D", "E" }, 68 },
{{ "E", "A" }, 32 },
{{ "A", "F" }, 45 },
{{ "B", "F" }, 25 },
{{ "C", "F" }, 40 },
{{ "D", "F" }, 60 },
{{ "E", "F" }, 50 }
};
struct range
{
char *point; //пункт
int distance; //расстояние от начальной точки
};
int main()
{
int i, j, c, current_distance, q, p, real_p;
char *current_city=NULL, line[ M ][ 50 ];
for( i=0; i<M; i++ )
line[ i ][ 0 ]='\0';
range *xr=new range[ M ];
//расстояние от стартовой точки до остальных изначально
//равно бесконечности
for( i=0; i<M; i++ )
{
xr[ i ].point=NULL;
xr[ i ].distance=INFINITY;
}
//а начальная имеет значение ноль
xr[ 0 ].distance=0;
xr[ 0 ].point=cities[ dance ];
for( i=0, c=0, p=1; i<M; i++ )
{
current_city=xr[ i ].point;
for( j=0, real_p=1; j<N; j++ )
{
current_distance=xr[ i ].distance;
if( strcmp(inf[ j ].points[ 0 ], current_city)==0
|| strcmp(inf[ j ].points[ 1 ], current_city)==0 )
{
//проверка не проверяли ли эту точку ранее
for( q=0; q<i; q++ )
if( strcmp(inf[ j ].points[ 0 ], xr[ q ].point)==0
|| strcmp(inf[ j ].points[ 1 ], xr[ q ].point)==0 )
break;
if( q<i )
continue;
//-----------------------------
//находим какая точка сейчас явл соседом с той которую
//проверяем т.е до какой точки смотрим расстояние
for( q=0; q<2; q++ )
if( strcmp(inf[ j ].points[ q ], current_city)!=0 )
break;
//i -- текущий пункт
//p -- всего соседей(уже посещенных)
//real_p -- сосед текущего пункта который сейчас проверяется
//j -- текущий отрезок
//q -- олределяет каой из двух пунктов inf[ j ].points явл текущим
// и стал-быть какой есть сосед
for( c=0; c<p; c++ )
if( strcmp(xr[ c ].point, inf[ j ].points[ q ])==0 )
break;
if( c<p )
real_p=c; //пункт посещался сверяться будем с ним
else
{ //пункт не посещался
xr[ p ].point=inf[ j ].points[ q ]; //запоминаем пункт
real_p=p; //вносим свежие данные по нему
++p;
}
current_distance+=inf[ j ].distance;
if( current_distance<xr[ real_p ].distance )
{
//запоминаем расстояние
xr[ real_p ].distance=current_distance;
strcat( line[ real_p ], inf[ j ].points[ 0 ] );
strcat( line[ real_p ], inf[ j ].points[ 1 ] );
}
}
}
}
cout << endl << "---------------------" << endl
<< "Beeline from " << xr[ 0 ].point << endl;
for( q=1; q<p; q++ )
cout << "to: " << xr[ q ].point << " = " << xr[ q ].distance
<< " ( " << line[ q ] << " ) " << endl;
getch();
return 0;
}
|
Здесь правда нахождение наименьшего расстояния но почти то, переделывать тоже некогда. Вместо расстояния взять стоимость и все! |
)