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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Kill100
405 / 271 / 37
Регистрация: 11.12.2010
Сообщений: 1,155
Завершенные тесты: 1
#1

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

18.03.2011, 13:56. Просмотров 1176. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.03.2011, 13:56
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм фронт волны в графе (C++):

Жадный алгоритм на графе - C++
Собственно, нужно написать программу поиска кратчайшего пути на графе &quot;жадным методом&quot;. То есть, дан ориентированный взвешенный граф (можно...

Алгоритм поиска в глубину в ориентированном графе - C++
Добрый вечер,форумчане:) Знаю, что подобная тема встречалась тут довольно часто, но у меня все-таки возник вопрос ответ на который я не...

Нахождение кратчайшего пути в графе, алгоритм Уоршелла - C++
Привет всем! алгоритм уоршелла, нужно найти кратчайший путь в графе. ввожу матрицу 0 1 5 1 0 2 5 2 0 работает нормально, все...

Алгоритм Брона-Кербоша или поиск клик в графе - C++
Собственно озадачился решением одной задачи: имеется матрица весов взвешенного ориентированного графа: {0, 6, 0, 5, 4}, {0, 0, 4, 0,...

Алгоритм Габова для поиска максимального паросочетания в произвольном графе за O(V^3) - C++
Прокомментируйте каждую строку. Очень нужно. Спасибо! #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;queue&gt; using namespace std;...

Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе) - C++
UNIT1 unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs,...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
18.03.2011, 15:45 #2
http://comp-science.narod.ru/KPG/Deikstr.htm
Там есть и листинг алгоритма на Си (скрытым текстом)
0
Kill100
405 / 271 / 37
Регистрация: 11.12.2010
Сообщений: 1,155
Завершенные тесты: 1
18.03.2011, 16:29  [ТС] #3
Цитата Сообщение от Day Посмотреть сообщение
http://comp-science.narod.ru/KPG/Deikstr.htm
Там есть и листинг алгоритма на Си (скрытым текстом)
Так он вроде бы не принимает I и J начала
и I и J конца...

И задана матрица смежности Ag
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.03.2011, 16:29
Привет! Вот еще темы с ответами:

Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе - C++
Блин я уже так задолбался с этим заданием может кто нибудь поможет: Построить алгоритм поиска кратчайшего пути между двумя...

Эффективный алгоритм подсчета расстояний от произвольной вершины до всех стальных вершин в графе - C++
Реализовать в виде программы и исследовать эффективный алгоритм подсчета расстояний от произвольной вершины до всех стальных вершин в...

Нахождение К путей Минимальной суммарной длины Во взвешенном графе с неотрицательными весами(Алгоритм Йена). - C++
Нахождение К путей Минимальной суммарной длины Во взвешенном графе с неотрицательными весами(Алгоритм Йена). Вот тут у меня есть код...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru