動態逼近法：設立一個先進先出的隊列用來保存待優化的結點，優化時每次取出隊首結點u，并且用u點當前的最短路徑估計值對離開u點所指向的結點v進行松弛操作，如果v點的最短路徑估計值有所調整，且v點不在當前的隊列中，就將v點放入隊尾。這樣不斷從隊列中取出結點來進行松弛操作，直至隊列空為止。

#include <iostream>
#include <queue>
#include <cstring>
#define inf 1<<29
using namespace std;
int map[105][105];
int dict[105];
queue <int> Q;
bool vis[105];
int c[105];




void build_map(int n,int m)
{
? ? for(int i=0;i<=n;i++)
? ? for(int j=0;j<=n;j++)
? ? if(i==j)
? ? map[i][j]=0;
? ? else map[i][j]=inf;
? ? for(int i=0;i<m;i++)
? ? {
? ? ? ? int b,e,v;
? ? ? ? cin>>b>>e>>v;
? ? ? ? map[b][e]=map[e][b]=v;
? ? }
}


bool SPFA(int n,int x)
{
? ? for(int i=1;i<=n;i++)
? ? dict[i]=inf;
? ? dict[x]=0;
? ? memset(vis,false,sizeof(vis));
? ? memset(c,0,sizeof(c));
? ? Q.push(x);
? ? vis[x]=true;
? ? while(!Q.empty())
? ? {
? ? ? ? int q=Q.front();
? ? ? ? Q.pop();
? ? ? ? vis[q]=false;
? ? ? ? c[q]++;
? ? ? ? if(c[q]>n)
? ? ? ? return false;
? ? ? ? for(int i=1;i<=n;i++)
? ? ? ? {
? ? ? ? ? ? if(dict[i]>dict[q]+map[q][i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? dict[i]=dict[q]+map[q][i];
? ? ? ? ? ? ? ? if(!vis[i])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? Q.push(i);
? ? ? ? ? ? ? ? ? ? vis[i]=true;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return true;
}


int main()
{
? ? int n,m;
? ? while(cin>>n>>m&&n!=0&&m!=0)
? ? {
? ? ? ? build_map(n,m);
? ? ? ? if(SPFA(n,1))
? ? ? ? cout<<dict[n]<<endl;
? ? ? ? else
? ? ? ? cout<<"有負環"<<endl;
? ? }
}

總結

以上是生活随笔為你收集整理的SPFA总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。