任意の重みの値の最短の経路のBellman-Fordアルゴリズムの実現を求めます
1492 ワード
このブログのオリジナルの文章を転載した者は、出典を明記してください.
Bellman−Fordアルゴリズムは、要求される最短経路の図に負の数のエッジを含む場合を解決するために使用することができる.
アルゴリズムの基本思想:2つのノードの間に最短経路が存在する場合、この経路の各ノードは最大1回通過する(1回を超えると、経路にループがあることを説明し、正数ループであれば経路の重み値を増加させる;負のループであれば、最短経路は存在しない;ゼロループであれば、結果に影響しない).したがって,n−1回反復するだけで,開始点から他の各点まで最大n−1辺の最短経路で求めることができる.
Bellman−Fordアルゴリズムは、要求される最短経路の図に負の数のエッジを含む場合を解決するために使用することができる.
アルゴリズムの基本思想:2つのノードの間に最短経路が存在する場合、この経路の各ノードは最大1回通過する(1回を超えると、経路にループがあることを説明し、正数ループであれば経路の重み値を増加させる;負のループであれば、最短経路は存在しない;ゼロループであれば、結果に影響しない).したがって,n−1回反復するだけで,開始点から他の各点まで最大n−1辺の最短経路で求めることができる.
#include <iostream>
using namespace std;
const int MaxSize=10;
int arr[MaxSize][MaxSize];
int dist[MaxSize]; //
int path[MaxSize]; //
int numNode=0;
void createArr()
{
cin>>numNode;
for(int i=0;i<numNode;++i)
for(int j=0;j<numNode;++j)
cin>>arr[i][j];
}
// Bellman-Ford
// v
void BellmanFord(const int v)
{
//dist path
for(int i=0;i<numNode;++i)
{
dist[i]=arr[v][i];
if(i!=v)
path[i]=v;
else
path[i]=-1;
}
// n-1
for(int len=2;len<numNode;++len)
for(int u=0;u<numNode;++u)
if(u!=v)
{
// u , i u dist[u] ,
// dist[u]
for(int i=0;i<numNode;++i)
if(dist[u]>dist[i]+arr[i][u])
{
dist[u]=dist[i]+arr[i][u];
path[u]=i;
}
}
//
for(int i=0;i<numNode;++i)
cout<<dist[i]<<" ";
cout<<endl;
// ( )
int end=numNode-1;
while(path[end]!=-1)
{
cout<<path[end]<<" ";
end=path[end];
}
cout<<endl;
}
int main()
{
createArr();
BellmanFord(0);
}