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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
dixonich
2 / 2 / 0
Регистрация: 23.03.2011
Сообщений: 62
#1

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

13.05.2012, 14:38. Просмотров 1178. Ответов 0
Метки нет (Все метки)

Помогите, пожалуйста, понять, почему мой код не работает.

Найти кратчайший 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++
Доброго времени суток. Есть кривой код: #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; const int inf = 1555; struct...

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

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

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

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

Алгоритм Форда - C++
Здравствуйте, помогите пожалуйста с задачей. Дан граф. Каждой дуге приписано некоторое число (вес) cij.Найти все кратчайшие пути между...

Алгоритм Форда-Белмана - C++
Найти расстояние от фиксированной вершины до всех остальных вершин графа. Для задания любая матрица 5*5. Программа на языке С++.

Алгоритм Форда-Фалкерсона, программа выводит ноль - C++
в чем проблема?вроде матрица инициализируется раз выводит первоначальную матрицу это алгоритм форда-фалкерсона. #include &lt;iostream&gt; ...

Входные данные. Метод Форда-Фалкерсона - C++
Доброго времени суток! Есть код, который работает и справляется с основной задачей - нахождением максимального потока сети методом...

Алгоритм Беллмана-Форда - C#
Здравствуйте, уже какой день мучаюсь с реализацией этого алгоритма в С#, прочитал Википедию и мн-во других сайтов по поводу этого...

Алгоритм Форда-Беллмана. - Pascal
Поиск кратчайшего пути, а также обход в глубь для поиска всех путей.

Алгоритм Беллмана-Форда - Алгоритмы
В википедии описан такой алгоритм...


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

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

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