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

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

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

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

13.05.2012, 14:38. Просмотров 1204. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2012, 14:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос алгоритм Форда-Беллмана (C++):

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

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

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

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

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

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

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2012, 14:38
Привет! Вот еще темы с ответами:

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

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

Входные данные. Метод Форда-Фалкерсона - 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 =...


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

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

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