Bellman-Fordアルゴリズムの単一ソース最短パス問題


与えられた図がDAGであり、負のエッジが存在する場合、Dijkstraアルゴリズムは使用できません.この場合、図に負のループが存在しない限り、このアルゴリズムを使用して、ソースポイントから各ポイントまでの最短距離を得ることができます.
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int INF=999999;
const int maxn=100+10;
struct edge{
	int from,to,cost;
};
edge ed[maxn];
int d[maxn],n,m; //n vertexs {1,2,3....n},m edges. 
void Bellman_Ford(int s)
{
	for(int i=1;i<=n;i++)
		d[i]=INF;
	d[s]=0;
	while(1)
	{
		bool update=false;
		for(int i=0;i<m;i++)
		{
			edge e=ed[i];
			if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost)
			{
				d[e.to]=d[e.from]+e.cost;
				update=true;
			}
		}
		if(!update)break;
	}	
}
int main()
{
	while(cin>>n>>m)
	{
		for(int i=0;i<m;i++)
		{
			cin>>ed[i].from>>ed[i].to>>ed[i].cost;
		}
		int src;
		cin>>src;
		Bellman_Ford(src);
		for(int i=1;i<=n;i++)cout<<d[i]<<" ";
		cout<<endl;
	}
	return 0;
} 

このアルゴリズムは、負のループが存在するかどうかをチェックしていません.テスト例のセットを示します.
5 7
1 2 10
1 5 100
1 4 30
2 3 50
3 5 10
4 3 20
4 5 60
1
出力は、1番ノードからすべてのノードへの最短パスである必要があります.
0 10 50 30 60