与Dijkstra算法与Bellman-ford算法不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为Bellman-ford算法，其时间复杂度为O(VE)。有研究指出在随机情形下平均一个节点入队的次数不超过2次，因此算法平均的时间复杂度为O(E)，甚至优于使用堆优化过的Dijkstra算法。

最短路径问题的解决
浙大研究生复试2010年上机试题-最短路径问题
问题描述：
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

输入：输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。
(1 输出：一行有两个数， 最短距离及其花费。

接下来，咱们便利用SPFA 算法来解决此最短路径问题。
以下，便引用sunbaigui的代码来说明此问题：
声明几个变量：
int d[1005][2];
bool used[1005];
vectormap[1005];
int N,M,S,T; 建个数据结构：
struct Node
{
int x,y,z;
Node(int a=0,int b=0