Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Алгоритм фронт волны в графе - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Создание не бинарных деревьев http://www.cyberforum.ru/cpp-beginners/thread259675.html
Доброго времени суток. Возникла небольшая сложность в создании не бинарных деревьев. Смысл я понял: надо создать элемент с ключом и список или массив(как у меня) с его сыновьями. вот код:...
C++ int сумма char'ов Дано n шестизначных чисел. Если сумма первых трех цифр не совпадает с суммой последних трех, то вывести Yes, иначе No. Входной файл: input.txt Первая строка-n Следующие n строк-числа. Выходной... http://www.cyberforum.ru/cpp-beginners/thread259665.html
C++ Оператор IF. Как сравнить *char' ы ?
У меня передаётся параметр при запуске через командную строку *argv, и сравнивается с уже заданным *char; Вот сам код: #include <iostream> #include <stdio.h> #include <cstdlib> using...
C++ Практика. Прямоугольник и Окружность
Задача в принципе не сложная...Но так как я чайник в с++, для меня это нереально)) С клавиатуры вводятся координаты х и у- верхней левой точки прямоугольника, его ширина и высота, а так же...
C++ Использование функций-шаблонов http://www.cyberforum.ru/cpp-beginners/thread259640.html
Для работы с двумерными массивами арифметических типов данных разработать шаблоны ввода и вывода массива, и также шаблон для решения основной задачи: -> Если количество строк в массиве четное, то...
C++ Определить, попадает ли заданная точка в круг С клавиатуры вводятся координаты точки,также вводятся координаты центра круга и его радиус. Определить попадает ли заданная точка в круг подробнее

Показать сообщение отдельно
Kill100
406 / 272 / 37
Регистрация: 11.12.2010
Сообщений: 1,156
Завершенные тесты: 1

Алгоритм фронт волны в графе - C++

18.03.2011, 13:56. Просмотров 1191. Ответов 2
Метки (Все метки)

[C++]Алгоритм фронт фолны в графе
Помогите..
Дан граф Ag
И координаты начальной вершины i,j
и кординаты конечной
i1,j1
Найти кротчайший путь и вывести его на экран..
после 2х часовых мучений намучал такой код но он не работает

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#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];
                    cout<<i<<" "<<k;
                    break;
                }
            }
        }
     }
 
     return way;
}
 
int main() {
    int i, j;
    int from, to, size;
    int **array, *way;
 
    cout << "Algoritm volni.\nEnter graph Ag: ";
    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 << " stroka: ";
        for ( j = 0; j < size; j ++ ){
            cin >> array[i][j];
        }
    }
    cout << "Enter iz: ";
    cin >> from;
    cout << "Enter kyda: ";
    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 << "net vixoda.";
    else {
        i = 0;
        while ( way[i] != -1 && i <= size ){
            if ( i != 0 ) cout << "";
            cout << way[i] + 1;
            i++;
        }
    }
    system("pause"); 
    getchar();
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru