最短経路の4つの解法
最短経路の4つの解法
「図」を勉強している間に、一番短いパスという古典的な問題に出会ったことがあります.最短経路には4つの最も古典的な解法がある.くだらないことは言わないで、直接コードをつけます.
フロイドアルゴリズム
フロイドアルゴリズムの時間複雑度O(n³),マルチソース、負のエッジがなく、時効性が悪い.
ディジェストラ
ディジェストラの時間複雑度O(n²),単源、無負権、時効性が良い.
ベルマン・フォード
ベルマン・フォードの時間複雑度O(n²),単源、負権か否かを判断でき、時効性が良い.
SPFA-ベルマン・フォードキュー最適化
ベルマン・フォードキュー最適化の時間複雑度は最大O(nm),最小O(n)であり,単一ソースでは負の重みであるか否かを判断でき,時効性は相対的によい.最短パスの古典的な解法は上記の通りです.転載が必要な場合は説明してください.本文は終わりました、いいねを押してから行きましょうo( ̄▽ ̄)ブ
「図」を勉強している間に、一番短いパスという古典的な問題に出会ったことがあります.最短経路には4つの最も古典的な解法がある.くだらないことは言わないで、直接コードをつけます.
フロイドアルゴリズム
//Floyd-Warshall
#include
using namespace std;
const int M=999999;
int n,m,p1,p2,l;
int map[1000][1000];
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
if (i==j)
{
map[i][j]=0;
}
else
{
map[i][j]=M;
}
}
}
for (int i=1;i<=m;i++)
{
cin>>p1>>p2>>l;
map[p1][p2]=l;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (map[i][j] > map[i][k] + map[k][j]) {
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
cout<<map[i][j];
}
cout<<endl;
}
return 0;
}
フロイドアルゴリズムの時間複雑度O(n³),マルチソース、負のエッジがなく、時効性が悪い.
ディジェストラ
//Dijkstra
#include
using namespace std;
const int M=99999999;
int n,m,p1,p2,l,map[100][100],dis[1000],book[1000]={0},mi,u;
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
if (i==j)
{
map[i][j]=0;
}
else
{
map[i][j]=M;
}
}
}
for (int i=1;i<=m;i++)
{
cin>>p1>>p2>>l;
map[p1][p2]=l;
}
book[1]=1;
for (int i=1;i<=n;i++)
{
dis[i]=map[1][i];
}
for (int i=1;i<=n-1;i++)
{
mi=M;
for (int j=1;j<=n;j++)
{
if (dis[j]<mi&&book[j]==0)
{
mi=dis[j];
u=j;
}
}
book[u]=1;
for (int k=1;k<=n;k++)
{
if(map[u][k]<M)
{
if (dis[k]>dis[u]+map[u][k])
{
dis[k]=dis[u]+map[u][k];
}
}
}
}
for (int i=1;i<=n;i++)
{
cout<<dis[i]<<" ";
}
return 0;
}
ディジェストラの時間複雑度O(n²),単源、無負権、時効性が良い.
ベルマン・フォード
//Bellman-Ford
#include
using namespace std;
const int M=9999999;
int main()
{
int n,m;
cin>>n>>m;
int p1[100],p2[100],l[100];
int dis[1000];
for (int i=1;i<=m;i++)
{
cin>>p1[i]>>p2[i]>>l[i];
}
for (int i=1;i<=n;i++)
{
dis[i]=M;
}
dis[1]=0;
for (int i=1;i<=n-1;i++)
{
for (int j=1;j<=m;j++)
{
if (dis[p2[i]]>dis[p1[i]]+l[i])
{
dis[p2[i]]=dis[p1[i]]+l[i];
}
}
}
for (int i=1;i<=n;i++)
{
cout<<dis[i]<<" ";
}
return 0;
}
ベルマン・フォードの時間複雑度O(n²),単源、負権か否かを判断でき、時効性が良い.
SPFA-ベルマン・フォードキュー最適化
//SPFA
#include
using namespace std;
const int inf=9999999;
int main()
{
int n,m;
cin>>n>>m;
int p1[1000],p2[1000],l[1000];
int dis[1000];
int book[1000];
int first[1000];
int next[1000];
int que[1000]={0};
int tail=1,head=1;
int k;
for (int i=1;i<=n;i++)
{
dis[i]=inf;
}
dis[1]=0;
for (int i=1;i<=n;i++)
{
book[i]=0;
}
for (int i=1;i<=n;i++)
{
first[i]=-1;
}
int i;
for (i=1;i<=m;i++)
{
cin>>p1[i]>>p2[i]>>l[i];
next[i]=first[p1[i]];
first[p1[i]]=i;
}
que[tail]=1;
tail++;
book[i]=1;
while (head<tail)
{
k=first[que[head]];
while(k!=1)
{
if (dis[p2[k]]>dis[p1[k]]+l[k])
{
dis[p2[k]]=dis[p1[k]]+l[k];
}
if (book[p2[k]]==0)
{
que[tail]=p2[k];
tail++;
book[p2[k]]=1;
}
}
k=next[k];
head++;
}
for (i=1;i<=n;i++)
{
cout<<dis[i]<<" ";
}
return 0;
}
ベルマン・フォードキュー最適化の時間複雑度は最大O(nm),最小O(n)であり,単一ソースでは負の重みであるか否かを判断でき,時効性は相対的によい.最短パスの古典的な解法は上記の通りです.転載が必要な場合は説明してください.本文は終わりました、いいねを押してから行きましょうo( ̄▽ ̄)ブ