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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Как считать только символы типа float из файла http://www.cyberforum.ru/cpp-beginners/thread573013.html
Как считать только десятичные дроби из файла типа .dat в котором помимо этого присутствуют другие символы?
C++ Ошибки LNK2019 Доброго дня всем! При описании класса - наследника шаблонного класса - вылезли следующие ошибки: Error 1: error LNK2019: unresolved external symbol "public: __thiscall MyList<class... http://www.cyberforum.ru/cpp-beginners/thread573003.html
C++ указатели
#include "stdafx.h" #include "conio.h" #include "iostream" #include "string" using namespace std; char *getname(void); int _tmain(int argc, _TCHAR* argv)
Минимальное реберное покрытие графа C++
Господа, подскажите пожалуйста, как реализовать эту задачу. Я так понимаю суть ее заключается ее в том, что,s необходимо найти такое множество ребер во взвешенном графе, которое бы охватывало все...
C++ Число простых делителей не превосходящих х на С++ рекурсивно http://www.cyberforum.ru/cpp-beginners/thread572971.html
Салют,народ! Помогите пожалуйста.Срочно нужна задачка: Найти число простых делителей не превосходящих х решённая рекурсивно.
C++ Вычислить сумму бесконечного ряда с помощью функций! Такая вот задача: Вычислить и напечатать сумму членов бесконечного ряда для заданного значения х с точностью до эпсилонт=0,00001:Вычисление слагаемого и суммы оформить в виде функций.Фото ряда... подробнее

Показать сообщение отдельно
dixonich
2 / 2 / 0
Регистрация: 23.03.2011
Сообщений: 62

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

13.05.2012, 14:38. Просмотров 1199. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru