与Dijkstra算法一样，我们定义一幅加权有向图的结构如下：
//带权有向图
struct EdgeWeightedDigraph
{size_t V; //顶点数size_t E; //边数map<int, forward_list<tuple<int, int, double>> adj; //改进后的邻接表，tuple存储的是边集
}
Bellman-Ford算法
在加权有向图的最短路径求解算法中，Dijkstra算法只能处理所有边的权值都是非负的图（是否有环不影响求解），而基于拓扑顺序的算法虽然能在线性时间内高效处理负权重图，但仅局限于无环图。为此还需要一个更为普遍的最短路径求解算法：能够处理负权重图，也能处理有环的情况。
Bellman-Ford算法是求含负权重图的单源最短路径的一种算法。其原理为连续进行松弛，对于含有V个顶点的加权有向图，在每次松弛时把每条边都更新一下，若在V-1次松弛后还能更新，则说明图中有负权重环，因此无法得出结果，否则就完成。
vector<int> Bellman-Ford(EdgeWeightedDigraph &g)
{vector<int> edge(g.V);//定义并初始化dis[]vector<double> dis(g.V, DBL_MAX);dis.at(0) = 0.0;//进行V-1次松弛for (size_t i = 0; i < g.V-1; ++i) //松弛计数{for (auto ite = g.adj.cbegin(); ite != g.adj.cend(); ++ite){for (const auto &e : (*ite).second) //松弛操作{if (dis.at(get<0>(e)) + get<2>(e) < dis.at(get<1>(e))){dis.at(get<1>(e)) = dis.at(get<0>(e)) + get<2>(e);edge.at(get<1>(e)) = get<0>(e);}}}}//判断是否存在负权重环for (auto ite = g.adj.cbegin(); ite != g.adj.cend(); ++ite){for (const auto &e : (*ite).second){if (dis.at(get<0>(e)) + get<2>(e) < dis.at(get<1>(e))){cerr << "含有负权重环，无解\n";vector<int> tmp;return tmp;}}}return edge;
}性能
朴素的Bellman-Ford算法实现非常简单，在每一轮迭代中都会放松E条边，共进行V轮迭代，因此时间复杂度为O(VE)。这种实现在实际应用中并不常见，因为它的效率不高，而且我们只需要对Bellman-Ford算法稍作修改就能大幅提高在一般场景下的运行时间。
SPFA算法
分析Bellman-Ford算法，最外层循环（迭代次数）V-1实际上是算法是否有解的上限，因为需要的迭代遍数等于最短路径树的高度。如果不存在负权重环，平均情况下的最短路径树的高度应该远远小于V-1，在此情况下，多余最短路径树高的迭代遍数就是时间上的浪费，由此，可以依次来实施优化。
实际上，在任意一轮中许多边的松弛都不会成功：只有上一轮中的dis[]值发生变化的顶点指出的边才能够改变其他dis[]的值。即，从算法执行的角度来说，如果某一轮迭代中松弛操作未执行，说明此次迭代所有的边都没有被松弛，因此可以证明：至此后，边集中所有的边都不需要再被松弛，从而可以提前结束迭代过程。
为了实现这样的优化，我们可以用队列来记录松弛操作被成功执行的顶点。同时还需要一个向量mark[]来指示顶点是否已经存在于队列中，以防止将顶点重复插入队列。
vector<int> SPFA(EdgeWeightedDigraph &g)
{vector<int> edge(g.V);queue<int> q;vector<int> mark(g.V, 0);//定义并初始化dis[]vector<double> dis(g.V, DBL_MAX);dis.at(0) = 0.0;int v = (*g.adj.cbegin()).first;q.push(v);mark.at(v) = 1;int cnt = 0;while (!q.empty()){v = q.front();q.pop();mark.at(v) = 0;//松弛操作for (const auto &e : g.adj.at(v)){int w = get<1>(e);if (dis.at(v) + get<2>(e) < dis.at(w)){dis.at(w) = dis.at(v) + get<2>(e);edge.at(w) = v;if (mark.at(w) == 0){q.push(w);mark.at(w) = 1;}}if (++cnt % g.V == 0){cerr << "存在负权重环，无解\n";vector<int> tmp;return tmp;}}}return edge;
}性能
SPFA算法是Bellman-Ford算法的改进，一般情况下其路径长度的比较次数的数量级为O(E+V) 。但如果加权有向图中存在负权重环，由于每次都会有边被松弛，因而不可能提前终止外层循环。这对应了最坏情况，其时间复杂度仍旧为O(VE) 。