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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
dixonich
2 / 2 / 0
Регистрация: 23.03.2011
Сообщений: 62
13.05.2012, 14:38     алгоритм Форда-Беллмана #1
Помогите, пожалуйста, понять, почему мой код не работает.

Найти кратчайший v-w путь в сети с произвольными весами.
входной файл должен быть следующим
9
0
1 2 0
1 10 2 -1 0
1 3 3 10 0
2 10 3 3 6 2 7 -6 0
1 7 4 -2 3 10 0
5 8 6 15 8 2 9 1 0
6 5 9 1 0
0
1
8

выходной

В случае отсутствия пути в файл результатов необходимо записать "N", при наличии пути - "Y" и далее с новой строки весь путь. Путь начинается источником и заканчивается целью. Узлы отделяются друг от друга пробелами, вес пути вычисляется как сумма весов всех дуг, входящих в него и записыва- ется в третьей строке.


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
#include <fstream>
#include <limits>
using namespace std;
 
struct apex 
{ 
    int n; 
    int c; 
    apex *next;
};
apex *net;
int *A, *D,*parent;
int m,start,finish;
const int inf = numeric_limits<int>::max();
void readnet ()
{
    int r,k;
    apex *last, *temp;
    ifstream fi("in.txt");
    fi>>m;
    net = new apex [m+1];
    for (int i=1; i<m+1;i++)
    {
        net[i].n=i;
        net[i].c=0;
        net[i].next=0;
        last=&net[i];
        do{
            fi>>r;
            if (r) 
            {
                fi>>k;
                temp = new apex();
                temp->n=r;
                temp->c=k;
                last->next=temp;
                last=last->next;
            }
        } 
        while(r);
    } 
    fi>>start>>finish;
    fi.close();
}
void matrix_weight()
{
    A = new int [(m+1)*(m+1)];
    for (int i = 1;i < m+1; i++) 
    { 
        for (int j = 1; j <m + 1; j++)  A[i*(m+1) + j] = inf;   
        A[i*(m+1) + i]=0;
    }
    for (int i = 1;i < m+1;i++)
    {
        apex *temp=net[i].next;
        while(temp)
        {
            A[i*(m+1) + temp->n] = temp->c;
            temp = temp->next;
        }
    }
 
}
 
void fill_D()
{
    D = new int [m+1];
    parent = new int [m+1];
    D[start]=0;
    for (int v=1;v<m+1;v++) 
        if (v!=start)   
        {
            D[v]=A[start*(m+1) + v]; 
            parent[v]=start;}
    for (int k=2;k<m;k++)
        for (int v=1;v<m+1;v++) 
            if(v!=start)
                for (int w=1;w<m+1;w++)
                    if (D[v]>(D[w]+(A[w*(m+1) + v]==inf?(A[w*(m+1) + v]-D[w]):A[w*(m+1) + v])))
                    { 
                        D[v]=D[w]+A[w*(m+1) + v]; 
                        parent[v]=w;
                    }
}
 struct tknot 
 {
    int v; 
    tknot* next;
 } *stack;
void add_compon (tknot*& st, int v)
{
    tknot* us = new tknot;
    us->v = v;
    us->next = st;
    st = us;
}
void fill_stack()
{
    stack = 0;
    add_compon(stack,finish);
    int v = finish;
    while (v!=start) 
    {
        v=parent[v]; 
        add_compon(stack,v);
    }
}
 
int main()
{
    readnet();
    matrix_weight();
    fill_D();
    fill_stack();
    tknot *temp=stack->next;
    ofstream fo("out.txt");
    if (D[finish] == inf) 
        fo<<"N";
    else 
    { 
        fo<<"Y\n"<<start;
        while(temp) 
        { 
            fo<<" "<<temp->v; 
            temp=temp->next;
        }
        fo<<"\n"<<D[finish];
    }
    fo.close();
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2012, 14:38     алгоритм Форда-Беллмана
Посмотрите здесь:

Алгоритм Форда-Беллмана C++
алгоритм C++
Алгоритм Форда - Беллмана C++
Алгоритм C++
C++ Алгоритм Форда-Белмана
C++ Матрица Форда Беллмана и метод Дейкстра
Входные данные. Метод Форда-Фалкерсона C++
C++ Алгоритм Форда-Беллмана

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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