Bellman-ford隊列優化算法 SPFA算法 -开发者知识库

Bellman-ford隊列優化算法 SPFA算法 -开发者知识库,第1张

Bellman-ford隊列優化算法的核心在於

:繼承了bellman-ford算法的核心內容(鄰接表處理)

    利用隊列優化,減少了不必要的判斷


下面在代碼中進行詳解

#include"iostream"
#include"cstdio"
#define inf 9999999
using namespace std;


int u[100];         //u,v,w為鄰接表存儲邊信息的必要數組空間

int v[100];

int w[100];
int dis[100];         //記錄源點到其余個點的最短路
int first[100];        //記錄i為起點的第一個邊的編號
int next[100];        //記錄i號邊的下一條邊的編號
int n,m;
int book[100];        //判重是否點已經進入隊列
int queue[100];      //隊列
int head;
int tail;
int k;


int main()
{
cin>>n>>m;
for(int i=1;i<=n;i )                   //dis初始化
{
dis[i]=inf;
}
dis[1]=0;
for(int i=1;i<=n;i )                //first初始化
{
first[i]=-1;
}
for(int i=1;i<=m;i )
{
scanf("%d%d%d",&u[i],&v[i],&w[i]);                  //邊的錄入
next[i]=first[u[i]];
first[u[i]]=i;
}
queue[1]=1;
head=1;
tail=2;
book[1]=1;
while(head<tail)
{
k=first[queue[head]];         
while(k!=-1)
{
if(dis[v[k]]>dis[u[k]] w[k])
{
dis[v[k]]=dis[u[k]] w[k];
if(book[v[k]]==0)
{
book[v[k]]=1;
queue[tail]=v[k];
tail ;
}
}
k=next[k];
}
head ;
book[queue[head]]=0;
}
for(int i=1;i<=n;i )
{
printf("%d ",dis[i]);
}
return 0;
}

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复