Bellman-Fordのダイナミックプランニング実装
1532 ワード
このアルゴリズムを考えてからもう2日になりました.前にBellman-Fordアルゴリズムを送ったことがありますが、それは収縮法を使用しており、時間がかかります.そこで動的計画を試み始め,コードは以下のように負の値がある場合の解の最短経路を解決できるが,負のループを処理する機能はない.動的に計画された再帰関数で負の輪の判断を行う能力がないので(個人的にはAlgorithm designで「n-1!=n」と言うのは間違いがあると思います).再帰的外部で判断すると,この方法は収縮法に対する優位性を失い,時間的複雑さは等しくなる.だからあの大神は再帰関数の中で負の輪を判断することができて、教えてください.もちろんBellman-Fordアルゴリズムはこの問題を解決する最適なアルゴリズムではありませんが、動的計画を練習するために多くの時間を費やしました.
Have fun coding,i_human.Have fun coding,everyone!
THE CODE:
Have fun coding,i_human.Have fun coding,everyone!
THE CODE:
// Bellman-Ford solved by dynamic prgramming.cpp : 。
//
#include "stdafx.h"
#include
#define N 100
#define m 10000 //
using namespace std;
int find(int i,int t);
void prin();
int n,e,l;
int pre[2][N];
int edge[N][N];
int main()
{
int u,v,length;
cin>>n>>e;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
edge[i][j]=m;
}
}
for(int i=1;i<=n;i++)
{
pre[0][i]=-1;
pre[1][i]=m;
}
pre[0][1]=1; // 1
pre[1][1]=0;
for(int i=0;i>u>>v>>length;
edge[u][v]=length;
}
for(int k=2;k<=n;k++)
find(e,k);
prin();
system("pause");
return 0;
}
int find(int i,int t)
{
if(pre[0][t]!=-1 && t!=1)
return find(i-1,pre[0][t])+pre[1][t];
else if(t==1)
return 0;
else
{
int M=m;
for(int j=1;j<=n;j++)
{
if(edge[j][t]!=m && find(i-1,j)+edge[j][t]