Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/7: Рейтинг темы: голосов - 7, средняя оценка - 4.86
ronaldo
92 / 46 / 63
Регистрация: 16.06.2014
Сообщений: 376
1

Алгоритм Форда-Беллмана

20.02.2015, 13:52. Просмотров 1221. Ответов 4
Метки нет (Все метки)

Доброго времени суток. Есть кривой код:
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
#include <iostream>
#include <vector>
using namespace std;
const int inf = 1555;
struct edge {
    int a, b, cost;
}; 
int n=5, m=14, i;
vector<edge> e;
void solve() {
    vector<int> d (n, inf);
    d[0] = 0;
    for (;;) {
        bool any = false;
        for (int j=0; j<m; ++j)
            if (d[e[j].a] < inf)
                if (d[e[j].b] > d[e[j].a] + e[j].cost) {
                    d[e[j].b] = d[e[j].a] + e[j].cost;
                    any = true;for(i=0;i<n;i++) cout<<d[i]<<"\t";cout<<endl;
                }                
        if (!any)  break;
    }
    for(int i=1; i<n; i++)
        if(d[i]<inf)
            cout<<d[i]<<endl;
        else
            cout<<"NO"<<endl;    
} 
int main(){ 
    edge t;    
    for(i=0; i<m; i++)
    {
        if (i==0) {t.a=0;t.b=1;t.cost=25;}
        if (i==1) {t.a=1;t.b=0;t.cost=25;}
        if (i==2) {t.a=0;t.b=4;t.cost=2;}
        if (i==3) {t.a=4;t.b=0;t.cost=2;}
        if (i==4) {t.a=0;t.b=3;t.cost=7;}
        if (i==5) {t.a=3;t.b=0;t.cost=7;}
        if (i==6) {t.a=0;t.b=2;t.cost=15;}
        if (i==7) {t.a=2;t.b=0;t.cost=15;}
        if (i==8) {t.a=1;t.b=2;t.cost=6;}
        if (i==9) {t.a=2;t.b=1;t.cost=6;}
        if (i==10) {t.a=2;t.b=3;t.cost=4;}
        if (i==11) {t.a=3;t.b=2;t.cost=4;}
        if (i==12) {t.a=4;t.b=3;t.cost=3;}
        if (i==13) {t.a=3;t.b=4;t.cost=3;}      
        t.a--; t.b--;
        e.push_back(t);
    }
    solve();
    return 0;
}
Неправильно считает, если я правильно понимаю. Может кто-нибудь не предложить свой алгоритм, а исправить этот?

Добавлено через 22 часа 55 минут
Может кто-нибудь указать, где ошибка?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.02.2015, 13:52
Ответы с готовыми решениями:

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

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

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

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

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

4
nmcf
6274 / 5577 / 2537
Регистрация: 14.04.2014
Сообщений: 23,468
20.02.2015, 16:49 2
47-я строка для чего?
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
#include <cstdlib>
#include <iostream>
#include <limits>
#include <vector>
 
using std::cout;
using std::endl;
 
 
const int inf = std::numeric_limits<int>::max();
 
struct edge {
    int a, b, cost;
};
 
void solve(const std::vector<edge> &e, int n, int v)
{
    std::vector<int> d(n, inf);
    d[v] = 0;
 
    for (;;)
    {
        bool any = false;
        for (int j = 0; j < e.size(); ++j)
            if (d[e[j].a] < inf)
                if (d[e[j].b] > d[e[j].a] + e[j].cost)
                {
                    d[e[j].b] = d[e[j].a] + e[j].cost;
                    any = true;
                }
        if (!any) break;
    }
 
    for (int i = 1; i < n; ++i)
        if (d[i] != inf) cout << i << ": " << d[i] << endl;
        else cout << i << ": NO" << endl;    
} 
 
int main()
{
    int n = 5, m = 14;
    std::vector<edge> e;
 
    edge t;    
    for(int i = 0; i < m; ++i)
    {
        if (i==0) {t.a=0;t.b=1;t.cost=25;}
        if (i==1) {t.a=1;t.b=0;t.cost=25;}
 
        if (i==2) {t.a=0;t.b=4;t.cost=2;}
        if (i==3) {t.a=4;t.b=0;t.cost=2;}
 
        if (i==4) {t.a=0;t.b=3;t.cost=7;}
        if (i==5) {t.a=3;t.b=0;t.cost=7;}
 
        if (i==6) {t.a=0;t.b=2;t.cost=15;}
        if (i==7) {t.a=2;t.b=0;t.cost=15;}
 
        if (i==8) {t.a=1;t.b=2;t.cost=6;}
        if (i==9) {t.a=2;t.b=1;t.cost=6;}
 
        if (i==10) {t.a=2;t.b=3;t.cost=4;}
        if (i==11) {t.a=3;t.b=2;t.cost=4;}
 
        if (i==12) {t.a=4;t.b=3;t.cost=3;}
        if (i==13) {t.a=3;t.b=4;t.cost=3;}      
        e.push_back(t);
    }
 
    solve(e, n, 0);
 
 
    system("pause");
}
1
iliya785
23 / 23 / 12
Регистрация: 04.06.2014
Сообщений: 80
20.02.2015, 19:35 3
http://e-maxx.ru/algo/ford_bellman
1
ronaldo
92 / 46 / 63
Регистрация: 16.06.2014
Сообщений: 376
21.02.2015, 09:20  [ТС] 4
nmcf, можете пошаговую выдачу добавить?
0
nmcf
6274 / 5577 / 2537
Регистрация: 14.04.2014
Сообщений: 23,468
21.02.2015, 09:55 5
Лучший ответ Сообщение было отмечено ronaldo как решение

Решение

Сам, что ли, не можешь добавить?
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
#include <cstdlib>
#include <iostream>
#include <limits>
#include <vector>
 
using std::cout;
using std::endl;
 
 
const int inf = std::numeric_limits<int>::max();
 
struct edge {
    int a, b, cost;
};
 
void solve(const std::vector<edge> &e, int n, int v)
{
    std::vector<int> d(n, inf);
    d[v] = 0;
 
    for (;;)
    {
        bool any = false;
        for (int j = 0; j < e.size(); ++j)
            if (d[e[j].a] < inf)
                if (d[e[j].b] > d[e[j].a] + e[j].cost)
                {
                    d[e[j].b] = d[e[j].a] + e[j].cost;
                    any = true;
//========================================================
                    for (int i = 1; i < n; ++i)
                        if (d[i] != inf) cout << i << ": " << d[i] << endl;
                        else cout << i << ": NO" << endl;
                    cout << endl << endl;
//========================================================
                }
        if (!any) break;
    }
 } 
 
int main()
{
    int n = 5, m = 14;
    std::vector<edge> e;
 
    edge t;    
    for(int i = 0; i < m; ++i)
    {
        if (i==0) {t.a=0;t.b=1;t.cost=25;}
        if (i==1) {t.a=1;t.b=0;t.cost=25;}
 
        if (i==2) {t.a=0;t.b=4;t.cost=2;}
        if (i==3) {t.a=4;t.b=0;t.cost=2;}
 
        if (i==4) {t.a=0;t.b=3;t.cost=7;}
        if (i==5) {t.a=3;t.b=0;t.cost=7;}
 
        if (i==6) {t.a=0;t.b=2;t.cost=15;}
        if (i==7) {t.a=2;t.b=0;t.cost=15;}
 
        if (i==8) {t.a=1;t.b=2;t.cost=6;}
        if (i==9) {t.a=2;t.b=1;t.cost=6;}
 
        if (i==10) {t.a=2;t.b=3;t.cost=4;}
        if (i==11) {t.a=3;t.b=2;t.cost=4;}
 
        if (i==12) {t.a=4;t.b=3;t.cost=3;}
        if (i==13) {t.a=3;t.b=4;t.cost=3;}      
        e.push_back(t);
    }
 
    solve(e, n, 0);
 
 
    system("pause");
}
1
21.02.2015, 09:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.02.2015, 09:55

Алгоритм Форда
Здравствуйте, помогите пожалуйста с задачей. Дан граф. Каждой дуге приписано...

Алгоритм Форда-Белмана
Найти расстояние от фиксированной вершины до всех остальных вершин графа. Для...

Алгоритм Форда-Фалкерсона, программа выводит ноль
в чем проблема?вроде матрица инициализируется раз выводит первоначальную...


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

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

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