Форум программистов, компьютерный форум 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 Product>::MyList<class Product>(void)" (??0?$MyList@VProduct@@@@QAE@XZ) referenced in function "public: __thiscall CD::CD(void)" (??0CD@@QAE@XZ) CD.obj Error 2: error LNK2019: unresolved external symbol "public:... 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:Вычисление слагаемого и суммы оформить в виде функций.Фото ряда находится во вложении! Вот я написал программу, но она, при задании значений x от 0 до 5 - выдает ответ (-1), а если задаю больше-программа зацикливается...Если я ставлю точку останова и просматриваю... подробнее

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

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

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