Задача използваща алгоритъм на Дейкстра

Изтегляне 73 Kb.

страница	2/4
Дата	03.01.2022
Размер	73 Kb.
	#112980
Тип	Задача

1 2 3 4

Алгоритъм-на-Дейкстра

Задача използваща алгоритъм на Дейкстра:

#include

#include
using namespace std;
/*

Алгоритъм на Дейкстра:

Постановка на задачата: Даден е краен ориентиран претеглен граф G(V, E). Тегловата функия на G приема неотрицателни стойност.

Даден е начален връх, да се намерят най-късите пътища от началния връх до всички останали върхове в графа.

Алгоритъм:

Ще стройм дървото на най-късите пътища постепенно, като ще започнем от началния връх и на всяка стъпка ще добавяме по един връх,

за целта ще използваме масива used:
used[ i ] = true <=> върха i е в дървото на най-късите пътища

used[ i ] = false <=> върха i не е в дървото на най-късите пътища

Ще използваме още 2 масива distance и parent. В distance ще пазим дължината на текущия най-къс път до всеки връх, а в parent бащата

на върха в дървото на най-кратките пътища. Първоначално

distance[ i ] = E[ начакния връх ][ i ] ако E[ начакния връх ][ i ] съществува

distance[ i ] = безкрайност ако E[ начакния връх ][ i ] не съществува

parent[ i ] = началния връх
На всяка стъпка избираме най-близкия връх, които не е включен в дървото и го добавяме. След това за всички върхове които не са

включени в дървото преизчисляваме distance.

distance[ i ] = min( distance[ i ], distance[ новодобавения връх ] + E[ новодобавения връх ][ i ] ) ако E[ новодобавения връх ][ i ] съществува

distance[ i ] = distance[ i ] ако E[ новодобавения връх ][ i ] не съществува

*/
void main()

{

// брой върхове в графа

int n;

cin >> n;

// достатъчно голяма стойност която ще използваме вместо безкрайност (сумата на всички ребра + 1)

double max = 1.0;

// прочитане на матрицата на съседство

double** graph = new double*[ n ];

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

{

graph[ i ] = new double[ n ];

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

{

cin >> graph[ i ][ j ];

if( 0 < graph[ i ][ j ] )

max += graph[ i ][ j ];

}

}

// прочитане на началния връх

int begin;

cin >> begin;

// инициализиране нa текущите най-малки разтояния

double* distance = new double[ n ];

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

{

if( 0 <= graph[ begin ][ i ] )

distance[ i ] = graph[ begin ][ i ];

else

distance[ i ] = max;

}
// инициализиране нa текущия баща в дърво на най-късите пътища

int* parent = new int[ n ];

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

parent[ i ] = begin;

// инициализиране нa множеството на върховете които участват в дървото

bool* used = new bool[ n ];

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

used[ i ] = false;
used[ begin ] = true;
for( int i = 0; i < n - 1; i++ )

{

int min_index = -1;

double min_value = max;
// намиране на най-близкия не добавен връх

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

if( !used[ j ] && min_value > distance[ j ] )

{

min_index = j;

min_value = distance[ j ];

}
// добавяне на минималния връх и преизчисляване на разтоянията до другите върхове

used[ min_index ] = true;

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

if( !used[ j ] && graph[ min_index ][ j ] > 0 && distance[ j ] > distance[ min_index ] + graph[ min_index ][ j ] )

{

parent[ j ] = min_index;

distance[ j ] = distance[ min_index ] + graph[ min_index ][ j ];

}

//извеждане на най-кратките разтояния

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

{

cout << i << ":\t" << distance[ i ] << endl;

stack< int > path;

path.push( i );

while( begin != path.top() )

path.push( parent[ path.top() ] );

cout << path.top();

path.pop();

while( !path.empty() )

{

cout << " -> " << path.top();

path.pop();

}
cout << endl;

}
delete used;

delete parent;

delete distance;

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

delete graph[ i ];
delete graph;

}

Изтегляне 73 Kb.

Сподели с приятели:

1 2 3 4