벨만-포드 알고리즘

간선의 갯수를 1부터 n-1까지 탐색하면서

 

최적의 경로를 찾는다.

 

다익스트라 알고리즘과 달리 간선의 값이 음수여도 사용이 가능하다.

#include <bits/stdc++.h>
using namespace std;

int dist[101];
struct Edge{
	int s;
	int e;
	int val;
	Edge(int a, int b, int c){
		s=a;
		e=b;
		val=c;
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i,n,m,a,b,c,j,s,e;
	vector<Edge> Ed;
	scanf("%d %d", &n, &m);
	
	for(i=1; i<=m; i++){
		scanf("%d %d %d",&a,&b,&c);
		Ed.push_back(Edge(a,b,c));
	}
	for(i=1; i<=n; i++){
		dist[i]=INT_MAX;
	}
	scanf("%d %d",&s,&e);
	dist[s]=0;
	for(i=1; i<n; i++){
		for(j=0; j<Ed.size(); j++){
			int s=Ed[j].s;
			int e=Ed[j].e;
			int w=Ed[j].val;
			if(dist[s]!=INT_MAX && dist[s]+w<dist[e]){
				dist[e]=dist[s]+w;
			}
		}

	}
	for(j=0; j<Ed.size();j++){
		int u=Ed[j].s;
		int v=Ed[j].e;
		int w=Ed[j].val;
		if(dist[u]!=INT_MAX && dist[u]+w<dist[v]){
			printf("-1\n");
			return 0;
		}
		
	}
	
	printf("%d\n", dist[e]);
	return 0;

}