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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Kill100
 Аватар для Kill100
359 / 248 / 33
Регистрация: 11.12.2010
Сообщений: 1,068
Завершенные тесты: 1
18.03.2011, 13:56     [C++]Алгоритм фронт фолны в графе #1
[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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.03.2011, 13:56     [C++]Алгоритм фронт фолны в графе
Посмотрите здесь:

C++ Алгоритм Габова для поиска максимального паросочетания в произвольном графе за O(V^3)
C++ Эффективный алгоритм подсчета расстояний от произвольной вершины до всех стальных вершин в графе
C++ Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе
C++ Жадный алгоритм на графе
Нахождение кратчайшего пути в графе, алгоритм Уоршелла C++
Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе) C++
Алгоритм Брона-Кербоша или поиск клик в графе C++
C++ Алгоритм поиска в глубину в ориентированном графе

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
18.03.2011, 15:45     [C++]Алгоритм фронт фолны в графе #2
http://comp-science.narod.ru/KPG/Deikstr.htm
Там есть и листинг алгоритма на Си (скрытым текстом)
Kill100
 Аватар для Kill100
359 / 248 / 33
Регистрация: 11.12.2010
Сообщений: 1,068
Завершенные тесты: 1
18.03.2011, 16:29  [ТС]     [C++]Алгоритм фронт фолны в графе #3
Цитата Сообщение от Day Посмотреть сообщение
http://comp-science.narod.ru/KPG/Deikstr.htm
Там есть и листинг алгоритма на Си (скрытым текстом)
Так он вроде бы не принимает I и J начала
и I и J конца...

И задана матрица смежности Ag
Yandex
Объявления
18.03.2011, 16:29     [C++]Алгоритм фронт фолны в графе
Ответ Создать тему
Опции темы

Текущее время: 00:50. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru