0 / 0 / 0
Регистрация: 26.09.2015
Сообщений: 3
1

Восстановление пути из алгоритма Форда-Беллмана

04.06.2016, 11:00. Показов 2679. Ответов 3
Метки нет (Все метки)

Реализовал алгоритм Форда-Беллмана, но не получается правильно восстановить пути, подскажите, где ошибаюсь.

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
112
113
114
115
116
117
118
119
120
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
 
using namespace std;
 
struct myStruct //для хранения пути
{
    vector<int> c;
    int iteration;
};
 
int main()
{
    setlocale(LC_ALL, "Russian");
    int a, s;
 
    cout << "Введите размерность матрицы: ";
    cin >> a;
 
    int **arr = new int*[a];
    for (int count = 0; count < a; count++)
        arr[count] = new int[a];
    int *d = new int[a];
    myStruct *way = new myStruct[a];
 
    cout << "Введите матрицу: " << endl;
    for (int i = 0; i < a; i++) //ввод матрицы весов
    {
        for (int j = 0; j < a; j++)
        {
            cin >> arr[i][j];
        }
    }
    cout << endl;
 
    for (int i = 0; i < a; i++) //вывод матрицы весов
    {
        if (i == 0)
        {
            for (int k = i; k < a; k++)
            {
                cout << "\t" << "V" << k + 1;
            }
            cout << endl;
        }
 
        cout << "V" << i + 1 << "\t";
        for (int j = 0; j < a; j++)
        {
            cout << arr[i][j] << "\t";
        }
        cout << endl;
    }
 
    cout << "\n\n" << "Введите вершину, от которой будем считать минмальные пути: \n";
    cin >> s;
 
    s = s - 1;
 
    for (int i = 0; i < a; i++)
    {
        d[i] = 1000000; //вместо бесконечности
    }
    d[s] = 0;
 
    for (int k = 0; k < a; k++)
    {
        for (int v = 0; v < a; v++)
        {
            if (v == s) continue;
 
            for (int u = 0; u < a; u++)
            {
                if (d[v] > (d[u] + arr[u][v]))
                {
                    d[v] = d[u] + arr[u][v];
 
                    way[v].iteration = k; //записываю на какой итерации для данной вершины происходит корректировка пути
                    if (k > way[v].iteration) way[v].c.clear(); //если алгоритм на следующем шаге нашёл более оптимальный путь, то стираю старый
                    way[v].c.insert(way[v].c.begin(), u + 1); //записываю вершину из который пришёл в начало вектора, т. к. путь восстанавливается с конца
                }
            }
        }
    }
 
    for (int i = 0; i < a; i++) //вывожу расстояние минимальных путей до i-ой вершины
    {
        if (i == 0)
        {
            for (int k = i; k < a; k++)
            {
                cout << "\t" << "V" << k + 1;
            }
            cout << endl << "\t";
        }
        cout << d[i] << "\t";
    }
 
    cout << "\n\n";
    for (int i = 0; i < a; i++)
    {
        if (d[i] >= 1000000)
        {
            cout << "Нет пути из V" << s + 1 << " в V" << i + 1;
            continue;
        }
 
        cout << "Путь до V" << i + 1 << ": ";
        for (int j = 0; j < way[i].c.size(); j++)
        {
            cout << way[i].c[j];
        }
        cout << endl;
    }
 
    cout << "\n\n";
    system("pause");
    return 0;
}
Тестировал на матрице:
∞ ∞ 5 5 2 12
∞ ∞ ∞ ∞ ∞ 2
∞ 2 ∞ ∞ ∞ ∞
∞ 2 ∞ ∞ ∞ ∞
∞ ∞ 1 2 ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞
Исходная вершина: V1.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.06.2016, 11:00
Ответы с готовыми решениями:

Графы: реализация алгоритма Беллмана-Форда
Написать программу, реализующую алгоритм Беллмана-Форда.

Алгоритм Форда-Беллмана
Народ если есть у кого нибудь исходник выложите пожалуйста очень надо. А то везде одно и то же......

Алгоритм Форда - Беллмана
Помогите пожалуйста понять что не так у меня. ограничение времени на тест: 1 сек. ограничение...

Алгоритм Беллмана-Форда
Здравствуйте всем. Я вообще редко обращаюсь сюда за помощью решить задачу и стыдно как то, но я не...

3
836 / 639 / 940
Регистрация: 26.06.2015
Сообщений: 1,409
04.06.2016, 15:18 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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <limits.h>
int** matadj_input(std::istream& _in, int& n);
int** matadj_create(int n);
void  matadj_free(int** m, int n);
bool  shortestBF(int** mat, int n, int s, std::vector<int>& ds, std::vector<int>& ps);
void  trace_path(std::ostream& _out, int e, std::vector<int>& ds, std::vector<int>& ps);
 
int main(void){
    int   n;
    int** m;
 
/*  ввод из файла
    std::ifstream fp("file.txt");
    m = matadj_input(fp, n);
    fp.close();
*/
    //на 1-ой строке указывается кол-во вершин
    char str[] = "6\n"\
        "0 5 4 0 0 8\n"\
        "5 0 0 0 0 0\n"\
        "4 0 0 3 0 0\n"\
        "0 0 3 0 3 0\n"\
        "0 0 0 3 0 5\n"\
        "8 0 0 0 5 0";
    std::istringstream sp(str);
 
    m = matadj_input(sp, n);
    if(m == NULL)
        return 1;
 
    // поиск от первой вершины
    int s = 0;
 
    std::vector<int> ds, ps;
    if(shortestBF(m, n, s, ds, ps)){
        //вывести кратчайшие пути во все остальные вершины
        for(int i = 0; i < n; ++i){
            if(i != s)
                trace_path(std::cout, i, ds, ps);
        }
    } else
        std::cout << "error!" << std::endl;
 
    matadj_free(m, n);
    std::cin.get();
    return 0;
}
 
//алгоритм Беллмана-Форда
bool shortestBF(int** mat, int n, int s, std::vector<int>& ds, std::vector<int>& ps){
    bool neg = true;
    ds.resize(n, INT_MAX);
    ps.resize(n, INT_MAX);
 
    ds[s] = 0;
    for(int i = 0; i < n; ++i){
        neg = false;
        for(int r = 0; r < n; ++r) {
            for(int j = 0; j < n; ++j) {
                if(mat[r][j] == INT_MAX)
                    continue;
 
                if((ds[r] < INT_MAX) && (ds[j] > (ds[r] + mat[r][j]))) {
                    ds[j] = ds[r] + mat[r][j];
                    ps[j] = r;
                    neg   = true;
                }
            }
        }
    }
    return (! neg);
}
 
//вывод пути к конечной вершине
void trace_path(std::ostream& _out, int e, std::vector<int>& ds, std::vector<int>& ps){
    std::vector<int> p;
    if(ds[e] == INT_MAX){
        _out << "error path!" << std::endl;
        return;
    }
 
    _out << "cost: " << ds[e] << std::endl;
    _out << "path: ";
 
    p.push_back(e);
    for(int i = ps[e]; i != INT_MAX; i = ps[i]) // выделяем путь
        p.push_back(i);
 
    //выводим
    for(int j = p.size() - 1; j >= 0; --j)
        _out << p[j] << ' ';
 
    _out << std::endl << std::endl;
    p.clear();
}
 
//ввод матрицы смежности для неориентированного графа
int** matadj_input(std::istream& _in, int& n){
    n = 0;
    if(!(_in >> n) || (n <= 1) || _in.fail())
        return NULL;
 
    int** m = matadj_create(n);
    if(m == NULL)
        return NULL;
 
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(!(_in >> m[i][j]) || _in.fail()){
                matadj_free(m, n);
                return NULL;
            }
 
            if(m[i][j] == 0)
                m[i][j] = INT_MAX;
            m[j][i] = m[i][j];
        }
    }
    return m;
}
 
//создание
int** matadj_create(int n){
    int** m = new (std::nothrow) int*[n];
    if(m == NULL)
        return NULL;
    
    for(int i = 0; i < n; ++i){
        m[i] = new (std::nothrow) int[n];
        if(m[i] == NULL){
            for(int j = 0; j < i; ++j)
                delete[] m[j];
            delete[] m;
            m = NULL;
            break;
        }
 
        for(int j = 0; j < n; ++j)
            m[i][j] = INT_MAX;
    }
    return m;
}
 
//удаление
void matadj_free(int** m, int n){
    for(int i = 0; i < n; ++i)
        delete[] m[i];
    delete[] m;
}
1
0 / 0 / 0
Регистрация: 26.09.2015
Сообщений: 3
04.06.2016, 16:08  [ТС] 3
Спасибо, сейчас буду разбираться
0
0 / 0 / 0
Регистрация: 11.10.2020
Сообщений: 2
28.12.2020, 22:13 4
Цитата Сообщение от Геомеханик Посмотреть сообщение
for(int i = ps[e]; i != INT_MAX; i = ps[i])
С чего такая уверенность, что вершина будет недостижимой?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.12.2020, 22:13
Помогаю со студенческими работами здесь

Алгоритм Форда-Беллмана
Доброго времени суток. Есть кривой код: #include &lt;iostream&gt; #include &lt;vector&gt; using namespace...

Матрица Форда Беллмана и метод Дейкстра
Тут такая проблема , задали написать матрицу с помощью єтих методов/ вопрос : Как вставить сюда...

Псевдокод алгоритма Беллмана-Форда
У кого есть, скиньте, пожалуйста. Заранее спасибо!

Нахождение минимального пути по алгоритму Форда-Беллмана
Помогите пожалуйста. Не могу понять как выбрать из какой вершины в какую идти.


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru