Шпоры по МПиПА / Графы / Поиск кратчайшего пути методом фронта волны / C / Исходник / waveAlgorithm

#include "iostream.h"
#include "stdio.h"

int *waveAlgorithm( int **concatenationMatrix, int dimension, int fromNode, int toNode ){
	int **fronts;   // Для хранения фронта волны
	int i, j, k, step;
	int *way, *alreadyMarked;   // Для хранения найденного пути и уже однажды пройденных вершин
	bool find;

	fronts = new int*[dimension];		// инициализация переменных
	for ( i = 0; i < dimension; i++ )
		fronts[i] = new int[dimension];

	way = new int[dimension];
	alreadyMarked = new int[dimension];

	for ( i = 0; i < dimension; i ++ )
		for ( j = 0; j < dimension; j ++ ) 
			fronts[i][j] = -1;
	for ( i = 0; i < dimension; i ++ )
         alreadyMarked[i] = 0;
	for ( i = 0; i <= dimension; i ++ )
         way[i] = -1;

     fronts[0][0] = fromNode;
     step = 0; find = false;		// конец инициализации переменных

     // ищем путь - существует ли он вообще попутно заполняя матрицу фронтов волны
     while ( step < dimension && !find ){
         i = 0;
         k = 0;
         if ( fronts[step][0] == -1 ) break; // если на предыдущем шаге не найдено ни однй новой вершины - выход

         while ( fronts[step][i] > -1 ) {     // поиск всех вершин в которые можно попасть из текущего фронта
             for ( j = 0; j < dimension; j++ ) {
                 if ( concatenationMatrix[fronts[step][i]][j] > 0 && alreadyMarked[j] == 0 ) {                     
					 alreadyMarked[j] = 1;
                     fronts[step+1][k] = j;
                     k++;
				 }
             }
             i++;
         }
		 
         i = 0;    // определяем нашли ли мы искомую вершину
         while ( fronts[step + 1][i] > -1 ) {
             if ( fronts[step + 1][i] == toNode ) { 
                 find = true;
                 break;
             }
             i++;
         }
         step++;
     }
	 
     if ( find ) {	// если путь был найден - вычисляем маршрут
        way[step] = toNode;
		for ( i = step-1; i >= 0; i-- ) {
			for ( k = 0; k < dimension; k ++ ){
			    if ( concatenationMatrix[fronts[i][k]][way[i+1]] > 0 ) {
					way[i] = fronts[i][k];
					break;
				}
			}
		}
     }

     return way;
}

void main() {
	int i, j;
	int from, to, size;
	int **array, *way;

    cout << "Wave algoritm.\nEnter graph dimension: ";
    cin >> size;

	array = new int*[size];
	for ( i = 0; i < size; i++ ) {
		array[i] = new int[size];
	}
	way = new int[size+1];

	for ( i = 0; i < size; i ++ ){
		cout << "Enter " << i + 1 << " row: ";
		for ( j = 0; j < size; j ++ ){
			cin >> array[i][j];
		}
	}
	cout << "Enter From Node: ";
	cin >> from;
	cout << "Enter To Node: ";
	cin >> to;
	way = waveAlgorithm( array, size, from - 1, to - 1 );
	cout << "\nExist way from " << from << " to " << to << " ?\nAnswer: from " << from << " to " << to << " ";
	if ( way[0] == -1 ) 
		cout << "not exist.";
	else {
		i = 0;
		while ( way[i] != -1 && i <= size ){
			if ( i != 0 ) cout << " -> ";
			cout << way[i] + 1;
			i++;
		}
	}
    cout << "\nPress \"Enter\" to continue..." << endl; 
    getchar();
}