Определение кратчайших растояний
1) Алгоритм Декстера: имеется города и дороги, дороги имеют некоторую длину, найти кратчайший путь между заданными городами. В терминах теории графа более общее задача звучит так: в ориентированной, неориентированной или смешанной сети найти кратчайший путь из заданной вершины во всех остальных.
Данный алгоритм относится к жадным алгоритмам.
Алгоритм:
1) Стартовую вершину заносим в очередь(одномерную таблицу)
2) Начиная с текущей позиции вершины оределяем ближайшуя вершину и все достежимые вершины заносим в очередь.(одномерную таблицу)
3) Найденные ближайшие вершины определяем все достежимые вершины при этом вычисляем растояние от стартовой до найденных вершин. И эти вершины заносим в очередь.
4) Среди неотмеченных ищем минимальное растояние от стартовой вершины.
5) Повторяем пункт 2,4.
Для реализации алгоритма необходимо иметь 3 одномерных массива.
d - таблица растояний, visit - отметка о посещении вершины, way - путь
void Init()
{
int i, j;
cin>>n>>m>>start>>finish;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(i==j) A[i][j]=0;
else A[i][j]=Big;
D[i]=Big;
}
for(k=1;k<=m;k++)
{
cin>>i>>j>>d;
A[i][j]=d; A[j][i]=d;
}
}
void Print(int v)
{
if(v>0)
{
Print(way[v]);
cout<<v<<' ';
}
}
void Dejkstra()
{
int i,j,M;
D[0]=Big+1; D[start]=0;
for(i=1;i<=n;i++)
{
M=0;
for(j=1;j<=n;j++)
if(D[j]<D[M]&&!visit[j]) M=j;
visit[M]=1;
for(j=1;j<=n;j++)
if(D[j]>A[M][j]+D[M])
{
D[j]=A[M][j]+D[M];
way[j]=M;
}
}
}
Количество операций алгоритма Декстера O(n^2).
Алгоритм Флойда
|
|
|
Если необходимо определить кратчайшие пути между всеми вершинами обычно используется алгоритм Флойда.
c[i][j]
D[i][j][k] наименьшее расстояние между вершинами i*j если в качестве пересадочных разрешено использовать только вершины с номерами k. Тогда D[i][j][0]=c[i][j], D[i][j][k]=min(D[i][j][k], D[i][k+1][k]+D[k+1][j][k]).
Геометрически это озночает (рис 1)
Void Print (int i, int j)
{
if(P[i][j]==0 && i!=j) cout<<' '<<j;
else
{
Print(i, P[i][j]); Print(P[i][j],j);
}
}
Void Floid()
{
int i,j,k,r;
for(i=0;i<=n;i++) for(j=0;j<=n;j++) D[i][j]=A[i][j];
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
r=D[i][k]+D[k][j];
if(D[i][j]>r)
{
D[i][j]=r; D[j][i]=r;
P[i][j]=k; P[j][i]=k;
}
}
}
Количество операций O(n^3)
21.10.2015
Дата добавления: 2016-01-06; просмотров: 13; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!