首页 > 代码库 > SPFA算法
SPFA算法
提供两种spfa算法模板
1.链表储存:
1 /*--------------------------spfa链表储存*/ 2 const int N = 10100 ; 3 4 struct Edge{ 5 int to,w,nxt; 6 }e[100010]; 7 int head[N],p; 8 int dis[N]; 9 bool vis[N];10 queue <int> q;11 12 void spfa(int a) //a点到其他点的最短距离 13 {14 memset(dis,0x3f,sizeof(dis));15 vis[a] = true;16 q.push(a);17 dis[a] = 0;18 while(!q.empty())19 {20 int d = q.front();21 for(int i = head[d]; i ;i = e[i].nxt)22 {23 int w = e[i].w ,v = e[i].to;24 if(dis[d] + w < dis[v])25 {26 dis[v] = dis[d] + w;27 if(!vis[v])28 {29 q.push(v);30 vis[v] = true ; 31 }32 }33 }34 q.pop();35 vis[d] = false ;36 }37 }
2.数组储存
1 /*----------------------------------spfa数组储存*/ 2 const int N = 1010 ; 3 int map[N][N]; 4 int dis[N]; 5 bool vis[N]; 6 int n; 7 queue <int> q; 8 9 void spfa(int a)10 {11 memset(dis,0x3f,sizeof(dis));12 q.push(a);13 vis[a] = true;14 dis[a] = 0;15 while(!q.empty())16 {17 int d = q.front();18 for(int i=1;i<=n;++i)19 {20 if(map[d][i]!=0 && map[d][i]+dis[d] < dis[i])21 {22 dis[i] = dis[d] + map[d][i];23 if(!vis[i])24 {25 q.push(i);26 vis[i] = true; 27 }28 }29 }30 q.pop();31 vis[d] = false ; 32 }33 }
SPFA算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。