bellman-ford/bellman-ford-alg.cpp at master · thinkphp/bellman-ford · GitHub

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
#include <cstdio>
#include <queue>
#include <bitset>
#define oo ((1LL<<31) - 1)
#define FIN "bellmanford.in"
#define FOUT "bellmanford.out"
#define MAXN 50001

using namespace std;

int nodes,
    edges,
    distMin[ MAXN ],
    count[ MAXN ];

queue<int> Queue;
bitset<MAXN> in_Queue(0);

struct Node {

       int y,
           c;
       Node *next;
};

Node *Graph[ MAXN ];

void addEdge(const int x, const int y, const int c) {

     Node *newNode;

     newNode = new Node;
     newNode->y = y;
     newNode->c = c;
     newNode->next = Graph[ x ];
     Graph[ x ] = newNode;
};

void readData() {

     int X,
         Y,
         cost;

     FILE *fin = fopen(FIN, "r");

     fscanf(fin, "%d %d", &nodes, &edges);

     for(;edges; edges--) {

           fscanf(fin, "%d %d %d", &X, &Y, &cost);

           addEdge(X, Y, cost);
     }

     fclose( fin );

};

void BellmanFord() {

     FILE *fout = fopen(FOUT, "w");

     for(int i = 2; i <= nodes; i++) distMin[ i ] = oo;

     distMin[ 1 ] = 0;

     Queue.push( 1 );

     in_Queue[ 1 ] = 1;

     int x;

     while( !Queue.empty() ) {

            x = Queue.front();

            Queue.pop();

            in_Queue[ x ] = false;

            for(Node *p = Graph[ x ]; p; p = p->next) {

                     if( distMin[ p->y ] > distMin[ x ] + p->c ) {

                         distMin[ p->y ] = distMin[ x ] + p->c;

                         if(!in_Queue[ p->y ]) {

                             Queue.push( p->y );

                             in_Queue[ p->y ] = true;

                             if(++count[ p->y ] > nodes - 1) {

                                         fprintf(fout, "%s", "Ciclu negativ!");

                                         return;
                             }
                         }
                     }
            }
     }

     for(int j = 2; j <= nodes; j++) fprintf(fout, "%d ", distMin[ j ]);
};

int main() {

   readData();
   BellmanFord();

 return(0);
};