Bellman-Fordアルゴリズムの単一ソース最短パス問題
1202 ワード
与えられた図がDAGであり、負のエッジが存在する場合、Dijkstraアルゴリズムは使用できません.この場合、図に負のループが存在しない限り、このアルゴリズムを使用して、ソースポイントから各ポイントまでの最短距離を得ることができます.
このアルゴリズムは、負のループが存在するかどうかをチェックしていません.テスト例のセットを示します.
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
#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