这里我们再谈单源最短路径。在之前的博客中，我们了解到了求单源最短路径的迪杰斯特拉算法，但是需要指出的是，迪杰斯特拉算法是无法解决负权环问题的，因为很显然的是，存在负边权的有向图，随着update()操作最短路径将无限的变小。因此为了解决含负边权的最短路径问题，我们引入SPFA算法，该算法由段凡丁于1994年论文提出。有趣的是，据说在国际上SPFA这个名称并不被认可，关于其中的详情可以自行百度。

　　其实spfa算法和迪杰斯特拉算法很相似，但是又有不同之处。以下为spfa的实现：

#include 
     
      #include 
      
       using namespace std;const int MAXN = 100001;const int MAXM = 200001;const int INF = (1 << 31) - 1;struct Line {    int p;    int v;    int next;};struct Node {    int d;    bool book;};Node node[MAXN];Line line[MAXM];int h[MAXN];int que[MAXN * 2];int n, m, s, x, y, v, head, tail, now;void add(int x, int y, int v, int lID) {    line[lID].p = y;    line[lID].v = v;    line[lID].next = h[x];    h[x] = lID;}void spfa(int now) {    int k = h[now];    int p;    while(k) {        p = line[k].p;        if(node[p].d > (node[now].d + line[k].v)) {            node[p].d = node[now].d + line[k].v;            if(!node[p].book) {                que[tail] = p;                tail++;                node[p].book = true;            }        }        k = line[k].next;    }}int main() {    scanf("%d%d%d", &n, &m, &s);    for(int i = 1; i <= m; i++) {        scanf("%d%d%d", &x, &y, &v);        add(x, y, v, i);    }    for(int i = 1; i <= n; i++) {        node[i].book = false;        node[i].d = INF;    }    node[s].d = 0;    head = 1;    tail = 1;    que[tail] = s;    node[s].book = true;    tail++;    while(head < tail) {        now = que[head];        spfa(now);        node[now].book = false;        head++;    }    for(int i = 1; i <= n; i++) {        printf("%d ", node[i].d);    }    return 0;}
      
     

　　

 

　　

　　圆满完成。