有关概念：

　　最短路问题：若在图中的每一条边都有对应的权值，求从一点到另一点之间权值和最小的路径

　　SPFA算法的功能是求固定起点到图中其余各点的的最短路（单源最短路径）

　　约定：图中不存在负权环，用邻接表存储有向图，d_i存放从起点到结点i的最短路，q为队列，保存待处理节点

思路：

　　首先指定起点入队，取当前队头结点u，沿每一条与u相连的边向外扩展，对该边所指向的结点v松弛（比较当前d_v与当前d_u加此边长，更新最短路值d_v，以及最短路径pre_v）如果v不在队列中且更新了最短路值，v进队，直至队列中没有元素时终止

　　较于Dijkstra，SPFA能处理带负权的边，但如果点进队的次数过多，时间效率就不如前者高

1 #include
     
       2 #include
      
        3 #define MAXN 4 #define MAXM 5 #define INF 214748364 6 int n,m,cnt,d[MAXN],heads[MAXN],q[MAXN],pre[MAXN]; 7 int head,tail;//队头、队尾指针 8 bool viss[MAXN];//结点i是否在队列中 9 struct node10 {11     int u,v;12     int next;13     int val;14 }edge[MAXM];15 void add(int x,int y,int z)16 {17     edge[++cnt].u=x;18     edge[cnt].v=y;19     edge[cnt].next=heads[x];20     edge[cnt].val=z;21     heads[x]=cnt;22 }23 void SPFA()24 {25     head=1;tail=2;26     q[1]=1;27     viss[1]=1;//默认1为起点28     while(head
      
     

*参考：