SPFA的基本思路是：只有被修改過最短路的頂點，才有可能導致修改與它鄰接的頂點的最短路。于是很容易想到用一個隊列維護。
以下是我的代碼：
#include<stdio.h>
#define min(a,b) (a<b?a:b)
const long maxn=507;
const long INF=100000007;
typedef struct
{
long front,rear,count,item[maxn];
}queue;
void clear(queue &q)
{
q.count=0;
q.front=0;
q.rear=-1;
}
bool empty(queue &q)
{
return (q.count==0);
}
void push(queue &q,long x)
{
q.rear++;
q.item[q.rear]=x;
q.count++;
}
long pop(queue &q)
{
long x=q.item[q.front];
q.front++;
q.count--;
return x;
}
// Queue
typedef struct EDGE_NODE
{
long u,v,w;
struct EDGE_NODE *next;
}edge_node;
long n,m,d[maxn];
edge_node *a[maxn];
// Var
void insert(long begin,long end,long weight)
{
edge_node *p=new edge_node;
p->u=begin;p->v=end;p->w=weight;
p->next=a[begin]->next;
a[begin]->next=p;
}
bool bellman_ford(long s)
{
bool in[maxn];
long in_num[maxn];
queue q;clear(q);
edge_node *p;
for(long i=1;i<=n;i++)
{
d[i]=(i==s?0:INF);
in[i]=false;
in_num[i]=0;
}
push(q,s);
in[s]=true;
in_num[s]++;
while(!empty(q))
{
long i=pop(q);in[i]=false;
for(p=a[i]->next;p;p=p->next)
{
long j=p->v;
if(d[i]+p->w<d[j])
{
d[j]=d[i]+p->w;
if(!in[j])
{
push(q,j);
in[j]=true;
in_num[j]++;
if(in_num[j]>n) return false;
}
}
}
}
return true;
}
int main()
{
//*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
scanf("%ld%ld",&n,&m);
for(long i=1;i<=n;i++)
{
a[i]=new edge_node;
a[i]->next=NULL;
}
for(long i=1;i<=m;i++)
{
long a,b,w;
scanf("%ld%ld%ld",&a,&b,&w);
insert(a,b,w);
insert(b,a,w);
}
if(bellman_ford(1))
{
for(long i=1;i<=n;i++) printf("%ld ",d[i]);
putchar('\n');
}
else printf("Error\n");
return 0;
}
posted on 2010-01-06 18:17
lee1r 閱讀(183)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數據結構