接着一直持续下去，直到队列为空，算法结束。
代码：
for(int i = 1; i <= n; i++) book[i] = 0; //初始时都不在队列中 queue<int> que; que.push(1); //将结点1加入队列 book[1] = 1; //并打标记 while(!que.empty()) { int cur = que.empty(); //取出队首 for(int i = 1; i <= n; i++) { if(e[cur][i] != INF && dis[i] > dis[cur]+e[cur][i]) //若cur到i有边且能够松弛 { dis[i] = dis[cur]+e[cur][i]; //更新dis[i] if(book[i] == 0) //若i不在队列中则加入队列 { que.push(i); book[i] = 1; } } } que.pop(); //队首出队 book[cur] = 0; }这其实就是SPFA算法（队列优化的Bellman-Ford），它的关键思想就在于：只有那些在前一遍松弛中改变了最短路估计值的结点，才可能引起它们邻接点最短路估计值发生改变。
它也能够判断负权回路：如果某个点进入队列的次数超过n次，则存在负环。
最短路径算法的对比
附
文中的图片和部分文字来自《啊哈！算法》，博文所做的是整理书的内容和自己的想法。
上面全都用邻接矩阵存图是因为注重算法本身，矩阵存图好理解。但平时打题的时候最爱用邻接表，几乎不用邻接矩阵，因为常见的是稀疏图，也即边数 m << n^2，用邻接表存节省复杂度。请看：图的存储结构之邻接表（详解）