最短路SPFA 算法详解
适用范围：给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。 我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。
算法思想：我们用数组d记录每个结点的最短路径估计值，用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止
期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。
实现方法：
建立一个队列，初始时队列里只有起始点，再建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点作为起始点去刷新到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。
判断有无负环： 如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）
首先建立起始点a到其余各点的最短路径表格
首先源点a入队，当队列非空时： １、队首元素（a）出队，对以a为起始点的所有边的终点依次进行松弛操作（此处有b,c,d三个点），此时路径表格状态为：
在松弛时三个点的最短路径估值变小了，而这些点队列中都没有出现，这些点需要入队，此时，队列中新入队了三个结点b,c,d
队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e点），此时路径表格状态为：
在最短路径表中，e的最短路径估值也变小了，e在队列中不存在，因此e也要入队，此时队列中的元素为c，d，e
队首元素c点出队，对以c为起始点的所有边的终点依次进行松弛操作（此处有e,f两个点），此时路径表格状态为：
在最短路径表中，e，f的最短路径估值变小了，e在队列中存在，f不存在。因此e不用入队了，f要入队，此时队列中的元素为d，e，f
队首元素d点出队，对以d为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：
队首元素为e，，f，g。然后e点出对队，e只指向g，然后此时g的最短路径估值没有变小（松弛不成功），没有新结点入队，队列中元素为f，g，表格状态仍然为：
队首元素f点出队，对以f为起始点的所有边的终点依次进行松弛操作（此处有d，e，g三个点），此时路径表格状态为：
在最短路径表中，e，g的最短路径估值又变小，队列中无e点，e入队，队列中存在g这个点，g不用入队，此时队列中元素为g，e
队首元素g点出队，对以g为起始点的所有边的终点依次进行松弛操作（此处只有b点），此时路径表格状态为：
在最短路径表中，b的最短路径估值又变小，队列中无b点，b入队，此时队列中元素为e，b队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：
在最短路径表中，g的最短路径估值没变化（松弛不成功），此时队列中元素为b
队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e这个点），此时路径表格状态为：
在最短路径表中，e的最短路径估值没变化（松弛不成功），此时队列为空了
最终a到g的最短路径为１４。
注：理论部分为转载，代码为原创。
#include<iostream>#include<deque>#include<cstdio>#include<algorithm>using namespace std;const int MAXN = 110;const int MAXM = 10100;const int INF = 0x3f3f3f3f;struct Edge{int from, to, cap, next;};Edge edge[MAXM];int head[MAXN];int path[MAXN];int inqueue[MAXN];int dist[MAXN];int viscnt[MAXN];int cnt;void addedge( int from, int to, int cap ){edge[cnt].from = from;edge[cnt].to = to;edge[cnt].cap = cap;edge[cnt].next = head[from];head[from] = cnt++;}int relax(int u,int v,int c){if (dist[u] + c < dist[v]){dist[v] = dist[u] + c;return 1;}return 0;}bool SPFA( int src, int n ){deque<int> dq;memset( viscnt, 0, sizeof viscnt );memset( inqueue, 0, sizeof inqueue );memset( dist, INF, sizeof dist );memset( path, -1, sizeof path );inqueue[src] = 1;viscnt[src]++;dist[src] = 0;dq.push_back( src );while (!dq.empty()){int u = dq.front();dq.pop_front();inqueue[u] = 0;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if(dist[u] < INF&&relax( u, v, edge[i].cap )){path[v] = u;if(!inqueue[v]){inqueue[v] = 1;viscnt[v]++;if(viscnt[v] == n)return false;if(!dq.empty() && dist[v] <= dist[dq.front()])dq.push_front( v );elsedq.push_back( v );}}}}return true;}int main(){int n,m;while(cin >> n >> m &&n&&m){memset( head, -1, sizeof head );cnt = 0;for(int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;addedge( a, b, c );//在a->b添加一条负载为c的边addedge( b, a, c );}SPFA( 1, n );cout << dist[n] << endl;}return 0;}
“人”的结构就是相互支撑，“众”人的事业需要每个人的参与。
