BELMAN FORD

THUẬT TOÁN BELMAN FORD

#include<stdio.h>

#define IFNIT 9999
typedef struct{
	int n;
	int L[500][500];
}Graph;
void init_graph(Graph *G, int n){
	G->n=n;
	int i,j;
	for(i=1;i<=G->n;i++)
		for(j=1;j<=G->n;j++)
			G->L[i][j]=0;
}
void add_graph(Graph *G, int x, int y, int w){
	G->L[x][y]=w;
}
int mark[100];
int pi[100];
int p[100];
void Khoitao(Graph *G, int mark[], int pi[]){
	int i;
	for(i=1;i<=G->n;i++){
		pi[i]=IFNIT;
		mark[i]=0;
	}
}
void dijkstra(Graph *G, int s){ // doi ten thanh bellmen_ford
	int i,j,k;
	pi[s]=0;
	p[s]=-1;
	for(i=1;i<=G->n;i++){
		int min_pi=IFNIT;
		for(j=1;j<=G->n;j++){
			if(mark[j]==0 && pi[j]<min_pi){
				min_pi=pi[j];
				k=j;
			}
		}
		mark[k]=1;
		for(j=1;j<=G->n;j++){
			if(G->L[k][j]!=0 && mark[j]==0){
				if(pi[k]+G->L[k][j] <pi[j]){
					pi[j]=pi[k]+G->L[k][j];
					p[j]=k;
				}
			}
		}
	}
}
int main(){
	Graph G;
	int n,i,m,w;
	int u,v;
	freopen("dt.txt","r",stdin);
	scanf("%d%d",&n,&m);
	init_graph(&G,n);
	for(i=1;i<=m;i++){
			scanf("%d%d%d",&u,&v,&w);
			add_graph(&G,u,v,w);
		}
	int x;
	int dem=0;
	scanf("%d",&x);
	Khoitao(&G,mark,pi);
	dijkstra(&G,x);
	for(i=1;i<=G.n;i++){
		if(pi[i]<0)
			dem++;
	}
	if(dem>0)
		printf("YES");
	else
	printf("NO");
	return 0;		
}