图论

无权图

交通运输，社交网络，互联网，工作的安排，闹区活动等等都可以用到图论处理。图可以分成两大类，一类是无向图，就是没有方向的，就好像两个人都互相认识一样，有向图就是单方面的联系，一个人认识另一个人，但是另一个人确不认识。当然，无向图也可以看成是一种特殊的有向图。图还可以根据权值分成两类，有权图和无权图，也就是边的权值，无权值只是表示了这个边存在与否而已，有权图表示的就是这个边的重要性，也可以看成是长度等等。图还有一个重要是性质，就是连通性的问题

这个图就不是连通图了。

简单图：不存在自环边和平行边的图。

后面讲最小生成树这些，自环边这些没有什么意义，直接比较权值就好了。

图的表示方法有两种，图的核心就在于每一个点以及他们相连的边，通常我们就使用两种方法来表示，

邻接矩阵和邻接表。邻接矩阵就是用一个二维的矩阵来表示：

0表示不相连，0表示相连，当然了也可以表示成是True或者false，因为是一个无向图，所以这个邻接矩阵是对称的；同时也可以用邻接矩阵来表示有向图：

邻接表就是类似一个链表和数组的组合的数据结构了：

有向图也是类似。邻接表适合表示稀疏图，因为表示稀疏图所占用的空间最小，邻接矩阵适合表示稠密图，邻接矩阵的空间开好就是固定的了，不用完就浪费了，所以适合稠密图。实现就比较简单了。等等会从一个文件读进一个图再添加，首先是邻接矩阵的实现：

namespace Matrix {    class DenseGraph {    private:        int n, m;        bool directed;        vector
     
      
       > g;    public:        DenseGraph(int n, bool directed) {            this->n = n;            this->m = 0;            this->directed = directed;            for (int i = 0; i < n; ++i) {                g.emplace_back(vector
       
        (n, false));            }        }        ~DenseGraph() = default;        int V() {            return n;        }        int E() {            return m;        }        void addEdge(int v, int w) {            assert(v >= 0 && v < n);            assert(w >= 0 && w < n);            if (haveEdge(v, w)) {                return;            }            g[v][w] = true;            if (!this->directed) {                g[w][v] = true;            }            this->m++;        }        bool haveEdge(int v, int w) {            assert(v >= 0 && v < n);            assert(w >= 0 && w < n);            return g[v][w];        }    };}

点数确定，边数先为0，等等从文件读进去。使用一个vector来存储，当然创建一个二维矩阵也可以。邻接表也是一样：

namespace list {    class SparseGraph {    private:        int n, m;        bool directed;        vector
     
      
       > g;    public:        SparseGraph(int n, bool directed) {            this->n = n;            this->directed = directed;            this->m = 0;            for (int i = 0; i < n; ++i) {                g.emplace_back(vector
       
        ());            }        }        ~SparseGraph() = default;        int V() {            return n;        }        int E() {            return m;        }        void addEdge(int v, int w) {            assert(v >= 0 && v < n);            assert(w >= 0 && w < n);            if (haveEdge(v, w)) {                return;            }            g[v].emplace_back(w);            if (v != w && !this->directed) {                g[w].emplace_back(v);            }            this->m++;        }        bool haveEdge(int v, int w) {            assert(v >= 0 && v < n);            assert(w >= 0 && w < n);            for (auto var : g[v]) {                if (var == w) {                    return true;                }            }            return false;        }    };}

广度深度遍历

接下来就是图比较重要的操作，遍历操作，通过一个点来遍历相邻的邻边。通常比较常用的方法就是遍历操作，遍历每一个点，矩阵就看看是不是true，表就直接打印即可。但是这样在后面的广度遍历和深度遍历那么邻接表和邻接矩阵就要写两遍了，所以这里使用一个迭代器来操作，迭代器当做一个借口，返回当前这个点所连接的点是什么。

//interator        class adjIterator {        private:            SparseGraph &G;            int v;            int index;        public:            adjIterator(SparseGraph &graph, int v) : G(graph) {                assert(v < graph.n);                this->v = v;                this->index = 0;            }            int begin(){                if (!G.g[v].empty()){                    return G.g[v][this->index];                }                return -1;            }            int next(){                index ++;                if (index < G.g[v].size()){                    return G.g[v][index];                }                return -1;            }            bool end(){                return index >= G.g[v].size();            }        };

写成一个类，index来指示当前遍历到哪里了。这里的构造函数由于初始化的参数是一个引用变量，所以需要列表初始化，因为引用变量的初始化一定要列表初始化才可以。begin得到第一个元素，next下一个，end判断是否结束，和for三连是一样的。

对于邻接矩阵的遍历有些许不同：

class adjIterator{        private:            DenseGraph &G;            int v;            int index;        public:            adjIterator(DenseGraph &graph, int v): G(graph){                this->v = v;                this->index = -1;            }            int begin(){                index = -1;                return next();            }            int next(){                for (index += 1; index < G.V(); index ++){                    if (G.g[v][index]){                        return index;                    }                }                return -1;            }            bool end(){                return index >= G.V();            }        };

因为这个时候是遍历所有的点，是true的就输出，不是的跳过，所以这个时候begin第一个输出的就是第一个为treu的点而不是index为0的点了。所以设成-1，通过next来找第一个为true的点即可，之后其他的同样。现在添加一个工具类，从文件读入一个图：

第一行是节点数和边数，接下来就是边的两个端点。

template 
     
      class ReadGraph{public:    ReadGraph(Graph &graph, const string &filename){        ifstream file(filename);        string line;        int V, E;        assert(file.is_open());        assert(getline(file, line));        stringstream ss(line);        ss >> V >> E;        assert(V == graph.V());        for (int i = 0; i < E; ++i) {            assert(getline(file, line));            stringstream ss(line);            int a, b;            ss >> a >> b;            graph.addEdge(a, b);        }    }};

使用模板类，是为了可以把邻接矩阵和邻接表都读进来。接下来的操作都很简单了。接下来就是图比较重要的操作了，图的遍历了。图的操作分为两种广度优先遍历，深度优先遍历。首先是深度遍历，就是从一个节点开始遍历到不能再遍历为止，图和树不一样，图是存在了环的，如果遍历过了那就必须设置已读的标记。

比如从0开始，首先第一个是0，之后就是1,2，因为这两个节点是没有连接到其他节点的，之后就是5，5连接了034，但是0已经看过了，就遍历3，3遍历4之后回来，最后就剩下和3节点相连的6了。从深度优先遍历也可以看出这个图的连通分量是多少。如果一直都是深度没有断开过，那肯定就是1了。这个时候就体现出了迭代器的好处，很好的屏蔽了底层数据结构的区别，直接复用即可。深度优先搜索还有一个性质，可以求解联通分量。如果深度一次完了之后还没有被遍历到的点那么就不属于这个联通分量了。同时也可以求解两个点是不是连在一起的，在同一个联通分量的那么肯定就是相连的了，总体来看，还是和连通分量有关系。

using namespace std;template
     
      class Component {private:    int *id;    Graph &G;    bool *visited;    int Ccount;    void dfs(int v) {        visited[v] = true;        id[v] = Ccount;        cout << v << " ";        typename Graph::adjIterator adj(G, v);        for (int i = adj.begin(); !adj.end(); i = adj.next()) {            if (!visited[i]){                dfs(i);            }        }    }public:    Component(Graph &graph) : G(graph) {        visited = new bool[G.V()];        id = new int[G.V()];        Ccount = 0;        for (int i = 0; i < G.V(); ++i) {            visited[i] = false;            id[i] = -1;        }        for (int i = 0; i < G.V(); ++i) {            if (!visited[i]) {                dfs(i);                Ccount++;            }        }    }    int count(){        return Ccount;    }    bool isConnected(int v, int w){        return id[v] == id[w];    }    ~Component() {        delete [] visited;    }};

count用来计算连通分量的个数，id用来计算这些点是属于哪一个连通分量的，遍历这个点的所有点，这里就用迭代器很好的屏蔽了不同数据结构实现的区别，如果没有访问过那就从这个点开始深度优先，然后递归下去。既然id就是连通分量的代号，那么直接等于count即可。判断是不是在一个连通分量里面的就直接对比id即可。

深度优先还有一个很重要的应用，就是寻路。这里的寻路只是找到一条路而已，没有说是最短路，事实上很多时候都是随机路径，因为有时候遍历的顺序不一样，得到的路径也是不一样的。

template
     
      class Path {private:    bool *visited;    int *from;    Graph &G;    int s;    void dfs(int v) {        visited[v] = true;        typename Graph::adjIterator adj(G, v);        for (int i = adj.begin(); !adj.end(); i = adj.next()) {            if (!visited[i]) {                from[i] = v;                dfs(i);            }        }    }public:    Path(Graph graph, int s) : G(graph) {        assert(s >= 0 && s < G.V());        visited = new bool[G.V()];        from = new int[G.V()];        for (int i = 0; i < G.V(); ++i) {            visited[i] = false;            from[i] = -1;        }        this->s = s;        dfs(s);    }    ~Path() {        delete[] from;        delete[] visited;    }    void path(int w, vector
      
        &vec) {        stack
       
         s;        int p = w;        while (p != -1) {            s.push(p);            p = from[p];        }        vec.clear();        while (!s.empty()) {            vec.push_back(s.top());            s.pop();        }    }    bool hasPath(int w) {        assert(w >= 0 && w < G.V());        return visited[w];    }    void showPath(int w) {        for (int i = 0; i < G.V(); ++i) {            cout << visited[i] << " ";        }        vector
        
          vec;        path(w, vec);        for (auto v: vec) {            cout << v << " ";        }        cout << endl;    }};

visited查看这些节点有没有被访问过，from查看这个节点是哪里来的，DFS遍历如果这个节点是没有被访问过的，那就赋值看看他是从哪个节点过来的，最后显示即可。最后需要反向查找。

深度优先遍历如果是使用邻接表，那么复杂度就是 $O(V+E)$ 级别的，因为表是通过直接遍历得到的，遍历到是就是有边的节点；而矩阵的复杂度是 $O(V^2)$ ，遍历的次数一定是平方。

图的广度优先遍历也需要用到队列。首先把这个节点周围的放入队列，如果队列不为空，那就直接出来一个把出来的那个周围的节点也塞进去，以此类推。广度优先遍历在图里面也叫层序遍历，一层一层的来，所以，先遍历到的肯定比后遍历到的距离原点要短，所以如果这个图是无权图，是可以使用这种方法来找到最短路径。每一层都加上1即可。

template 
     
      class bfs{private:    Graph &G;    int s;    bool *visited;    int *from;    int *ord;public:    bfs(Graph &graph, int s): G(graph){        assert(s >= 0 && s < graph.V());        from = new int[graph.V()];        ord = new int[graph.V()];        visited = new bool[graph.V()];        for (int i = 0; i < graph.V(); ++i) {            visited[i] = false;            from[i] = -1;            ord[i] = -1;        }        this->s = s;        queue
      
        q;        q.push(s);        ord[s] = 0;        visited[s] = true;        while (!q.empty()){            int w = q.front();            cout << w << " ";            q.pop();            typename Graph::adjIterator adj(graph, w);            for (int i = adj.begin(); !adj.end(); i = adj.next()) {                if (!visited[i] ){                    q.push(i);                    visited[i] = true;                    from[i] = w;                    ord[i] = ord[w] + 1;                }            }        }    }    void showShortPath(int w){        stack
       
         s;        if (visited[w]){            int p = w;            while (p != -1){                s.push(p);                p = from[p];            }        }        vector
        
          vec;        while (!s.empty()){            vec.push_back(s.top());            s.pop();        }        for (auto v: vec) {            cout << v << " ";        }        cout << endl;    }};

from就是存储上一个节点，ord存储距离起始点的距离是多少。

BFS找到的就是最短路径。DFS其实也可以找到最短路径，但是是随机的，它和你存储图的顺序有不同，和图的结构也有关系，但是BFS是一定的，而且BFS的最短路径是不止一条。

带权图

上面所提到的都是无权图，就是仅仅是一条边而已，但是有权图每一条边都会带有一个权值，这个权值的意义可能是这条路的长度，平坦程度等等。上面的无权图有两种存储方式，那么自然有权图也有两种了，通过无权图变换过来。

里面原先填的是布尔类型，现在改成权值即可，但是邻接表就没有这么简单了。原先是要存储点即可，因为存在即合理，没有就没有了。带权就要存储两个信息：

这里存在一个接口不统一的问题，邻接表的类型将使用一个类来表达，如果邻接矩阵使用数字来表达权值，那么接口不统一返回的内容不一样就不能统一使用接口了。所以邻接矩阵也使用一个类来表达。修改很简单，只需要改变一下无权图的类而已。定义一个边类：

class Edge {private:    int a, b;    Weight weight;public:    Edge() {}    Edge(int a, int b, Weight weight) {        this->a = a;        this->b = b;        this->weight = weight;    }    ~Edge() = default;    Weight wt(){        return weight;    }    int Other(int v) {        assert(v == a || v == b);        return v == a ? b : a;    }    friend ostream& operator<<(ostream &os, const Edge &e){        os << e.a << "->" << e.b << " : " << e.weight;        return os;    }    bool operator<(Edge
     
      & e){        return weight < e.wt();    }    bool operator<=(Edge
      
       & e){        return weight <= e.wt();    }    bool operator>(Edge
       
        & e){        return weight < e.wt();    }    bool operator>=(Edge
        
         & e){        return weight < e.wt();    }    bool operator==(Edge
         
          & e){        return weight < e.wt();    }};

Edge类存储了起始点和终点和权值。重载了一些比较和输出符号，等一下的输出和比较都要用到。邻接矩阵需要修改的不多：

using namespace std;namespace Span {    template
     
          class DenseGraph {    private:        int n, m;        bool directed;        vector
      
       
        
          *>> g;    public:        DenseGraph(int n, bool directed) {            this->n = n;            this->m = 0;            this->directed = directed;            for (int i = 0; i < n; ++i) {                g.emplace_back(vector
         
          
            *>(n, NULL)); } } ~DenseGraph() { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (g[i][j] != NULL) { delete g[i][j]; } } } } int V() { return n; } int E() { return m; } void addEdge(int v, int w, Weight weight) { assert(v >= 0 && v < n); assert(w >= 0 && w < n); if (haveEdge(v, w)) { delete g[v][w]; if (!this->directed) { delete g[w][v]; } m--; } g[v][w] = new Edge
           
            (v, w, weight); if (!this->directed) { g[w][v] = new Edge
            
             (w, v, weight); } this->m++; } bool haveEdge(int v, int w) { assert(v >= 0 && v < n); assert(w >= 0 && w < n); return g[v][w] != NULL; } void show() { for (int i = 0; i < g.size(); ++i) { for (int j = 0; j < g[i].size(); ++j) { if (g[i][j] != NULL){ cout << g[i][j]->wt() << " "; } else{ cout << "NULL" << " "; } } cout << endl; } } class adjIterator { private: DenseGraph &G; int v; int index; public: adjIterator(DenseGraph &graph, int v) : G(graph) { this->v = v; this->index = -1; } Edge
             
               begin() { index = -1; return next(); } Edge
              
                next() { for (index += 1; index < G.V(); index++) { if (G.g[v][index]) { return G.g[v][index]; } } return NULL; } bool end() { return index >= G.V(); } }; };}

邻接表也是一样。

using namespace std;namespace Sparse {    template
     
          class SparseGraph {    private:        int n, m;        bool directed;        vector
      
       
        
          *>> g;    public:        void show() {            for (int i = 0; i < n; ++i) {                for (int j = 0; j < g[i].size(); ++j) {                    cout << g[i][j]->wt() << " ";                }                cout << endl;            }        }        SparseGraph(int n, bool directed) {            this->n = n;            this->directed = directed;            this->m = 0;            for (int i = 0; i < n; ++i) {                g.emplace_back(vector
         
          
            *>()); } } ~SparseGraph() { for (int i = 0; i < n; ++i) { for (int j = 0; j < g[i].size(); ++j) { delete g[i][j]; } } } int V() { return n; } int E() { return m; } void addEdge(int v, int w, Weight weight) { assert(v >= 0 && v < n); assert(w >= 0 && w < n); if (haveEdge(v, w)) { return; } g[v].emplace_back(new Edge
           
            (v, w, weight)); if (v != w && !this->directed) { g[w].emplace_back(new Edge
            
             (w, v, weight)); } this->m++; } bool haveEdge(int v, int w) { assert(v >= 0 && v < n); assert(w >= 0 && w < n); for (auto var : g[v]) { if (var->Other(v) == w) { return true; } } return false; } //interator class adjIterator { private: SparseGraph &G; int v; int index; public: adjIterator(SparseGraph &graph, int v) : G(graph) { assert(v < graph.n); this->v = v; this->index = 0; } int begin() { if (!G.g[v].empty()) { return G.g[v][this->index]; } return -1; } int next() { index++; if (index < G.g[v].size()) { return G.g[v][index]; } return -1; } bool end() { return index >= G.g[v].size(); } }; };}

修改一下show函数即可。

最小生成树

要讨论的第一个有权图问题就是最小生成树问题。对于一个完全连通的一个带权图能否找到这个图属于的一个最小生成树，这个生成树要连接所有的顶点，并且不能有环，因为树就没有环，而判断有没有环就可以用并查集来判断了。如果这棵树所有的权值相加都是最小的那么就叫做是最小生成树。电缆的布线问题就用到这些。最小生成树一般针对带权的无向图，并且需要连通，不连通怎么都到不了所有的节点。连通所有的点就需要找V-1条边，连接V个顶点。

首先要介绍一个切分定理。把图中的节点切分成两部分，成为一个切分。

蓝色和红色就是两部分了。同时如果这条边的两个端点是属于切分的不同的两边，那么这个边就称为横切边。

切分定理：给定任意的切分。横切边中权值最小的边就是最小生成树的一条边。现在简单证明一下，比如现在有两部分，这两部分就是被切分了的，他们之间有很多的横切边，如果没有那么这个图就不连通了。假设他们之间有一条不是最小值的横切边，而如果形成了最小生成树之后按照规则是要把最小的横切边添加进去，但是刚刚说了已经有一条不是最小值的横切边了，那么就会形成环，所以就需要删除掉不是最小的横切边。这个定理很重要，无论点的多少只要切分开了就可以使用这种方法进行一个点一个点的进行扩散。

Prim Algorithm

prim算法就是根据这个思想来完成最小生成树的构建。首先一开始所有点都是同一个阵营，首先遍历第一个点，也就是第0号点，那么这个点就出了这个阵营，把它相邻的边都扔进一个最小堆进行维护，如果当前的堆不是空的，那么就出第一个最小的边，但是出的时候需要判断这个边的两个顶点是不是不同阵营的，因为在遍历的过程中每一个点的阵营的改变的全局的，会影响到其他边本来的状态，所以取出来的时候需要判断一下，然后从取出来处理的那条边做突破口，看它两边的那个点是没有被访问的，继续上述步骤。准备一个marked boolean数组，false一边true一边，true表示被访问了，也就是被访问的一边没有被访问的一边。

namespace MinimumSpanTree_Prim {    template
     
          class Prim {    private:        Graph &G;        MinHeap
      
       
        > pq;        bool *marked;        vector
        
         
          > MinimumEdge;        Weight mstWeight;        void visit(int v){            assert( !marked[v] );            marked[v] = true;            typename Graph::adjIterator adj(G, v);            for (Edge
          
            *e = adj.begin(); !adj.end() ; e = adj.next()) { if (!marked[e->Other(v)]){ cout << e->wt() << " "; pq.insert(*e); } } cout << endl; pq.show(); } public: Prim(Graph &graph) : G(graph), pq(MinHeap
           
            
             >(G.E())){ marked = new bool[ G.V() ]; for (int i = 0; i < G.V(); ++i) { marked[i] = false; } MinimumEdge.clear(); visit(0); while ( !pq.isEmpty() ){ Edge
             
               e = pq.extractMin(); cout << e.wt() << endl; if (marked[e.v()] == marked[e.w()]){ continue; } MinimumEdge.push_back(e); if ( !marked[e.v()] ){ visit(e.v()); } else{ visit(e.w()); } } mstWeight = MinimumEdge[0].wt(); for (int j = 1; j < MinimumEdge.size(); ++j) { mstWeight += MinimumEdge[j].wt(); } } ~Prim(){ delete [] marked; } vector
              
               
                > mstEdges(){ return MinimumEdge; } Weight result(){ return mstWeight; } };}

访问这个节点的时候就遍历这个节点的所有边，塞进堆里面动态维护。

当最小堆不为空，那么就继续，所有while这个循环的复杂度就是E，也就是边数，而出堆的复杂度是 $logE$ ，visit中遍历的复杂度也是E，所以综上Lazy Prim的复杂度就是 $ElogE$ 。其实是可以改进算法实现 $ElogV$ 的。原来的算法是所有的边都要进入最小堆，但是随着算法进行很多时候堆里面的边已经不再是横切边了，而有时候我们关注的只是最短的一条横切边长的就不用管了。实现这个优化可以使用索引堆来实现，因为索引堆是只需要分配V个空间，每一个点只会保留和他距离最近的一条横切边。

Kruskal Algorithm

在寻找最短的一条边的时候，会不会每一次寻找最短的一条边都会是属于最小生成树的呢？其实就是这样，因为我们找到一个最短边之后就把这条最小边的一个点看做是另一个阵营，这样每一次我们只需要防止形成环就好了。首先先对所有的边进行排序，每一次取一条，只要不形成环即可。那么问题来了，怎么判断是不是环？之前提到了并查集，并查集就可以判断是不是形成环。

namespace MinimumSpanTree_Kruskal{    template 
     
          class Kruskal{    private:        vector
      
       
        > mst;        Weight mstWeight;    public:        Kruskal(Graph &graph){            MinHeap
        
         
          > pg(graph.E());            for (int i = 0; i < graph.V(); ++i) {                typename Graph :: adjIterator adj(graph, i);                for (Edge
          
            *e = adj.begin(); !adj.end() ; e = adj.next()) { if (e->v() < e->w()){ pg.insert(*e); } } } UF_version3::unionFind unionFind(graph.E()); while (!pg.isEmpty() && mst.size() < graph.V() - 1){ Edge
           
             e = pg.extractMin(); if (unionFind.isConnected(e.v(), e.w())){ continue; } mst.push_back(e); unionFind.unionElements(e.v(), e.w()); } mstWeight =mst[0].wt(); for (int j = 1; j < mst.size(); ++j) { mstWeight += mst[j].wt(); } } vector
            
             
              > mstEdges(){ return mst; } Weight result(){ return mstWeight; } };}

思路和实现都很简单，不用多逼逼。

Summary

因为Kruskal需要遍历所有的边，出堆的时候还需要logE，最后还需要比较，所有相对来说是慢一点的。

事实上这两种算法的思想是基本一致的，Prim算法是同通过一个点来找到最小的横切边，而Kruskal算法是直接找到最小的一条，如果没有环，那么最小的这个边一定是一端是一个阵营，一端是另外一个阵营。所有可以把其中的一端看成是Prim算法中选择的一个点，那个最小边就是横切边了，所有Prim算法是通过点找边，而Kruskal算法是通过边找点，虽然没有真正意义上的找，但是这种方式思考Prim和Kruskal是很相似的。

最短路径问题

最短路径问题理论上是对于有向图的，但是无向图本质上也是一种特殊的有向图，所以这里所写的最短路径对于无向图也是有效的。之前在无权图的时候是使用是广度遍历找到当前点到所有点的最短路径，而加上了权值之后不能单单从一次广度就判断那条边的最小的，因为权值的叠加可能更会使得最下的权值空前的增大。所以每一次都要在当前的节点判断一下，绕一下过后是不是比原来直接到达目的地的还要短，这个操作就叫做松弛操作。

dijkstra算法

使用dijkstra算法又前提条件，这个算法的权值是不能有负权值，算法的复杂度是 $ElogV$ 的，最小生成树Prim算法的改进也是这个复杂度。用一个最简单的图：

从0开始，第一次只有三条路径，5,2,6，那么这个时候到1,2,3的路径分别就是

，这个时候0-2就是最小的了，因为这个再经过松弛操作只能是变大不会变小，这也是为什么不能负权边的原因。确定新的节点的最短路径之后开始松弛操作，从2开始，这个时候到1更小，于是替换，到4还没有被访问，于是就是7，到三明显还是短的，所以就是5，于是更新：

以此类推。由于存储的节点的序号，但是比较的却是边的权值，所以用索引堆来处理，每一个点对应当前的最短路径。

template 
     
      class Dijkstra{private:    Graph &G;    int s;    Weight *distTo;    bool *marked;    vector
      
       
         *> from;public:    Dijkstra(Graph &graph, int s) : G(graph){        this->s = s;        distTo = new Weight[G.V()];        marked = new bool[G.V()];        for (int i = 0; i < G.V(); ++i) {            distTo[i] = Weight();            marked[i] = false;            from.push_back(NULL);        }        IndexMinHeap
        
          pq(G.V());        distTo[s] = Weight();        marked[s] = true;        pq.insert(s, distTo[s]);        while (!pq.isEmpty()){            int v = pq.extractMinIndex();            marked[v] = true;            typename Graph :: adjIterator adj(G, v);            for (auto e = adj.begin(); !adj.end(); e = adj.next()) {                int w = e->Other(v);                if (!marked[w]){                    if (from[w] == NULL || distTo[v] + e->wt() < distTo[w] ){                        distTo[w] = distTo[v] + e->wt();                        from[w] = e;                        if (pq.contain(w)){                            pq.change(w, distTo[w]);                        } else{                            pq.insert(w, distTo[w]);                        }                    }                }            }        }    }    void show(){        stack
         
          
            *> ss; for (int i = 1; i < G.V(); ++i) { vector
           
            
             > vec; cout << i << " :" << endl; Edge
             
               * e = from[i]; while (e->v() != this->s){ ss.push(e); e = from[e->v()]; } ss.push(e); while( !ss.empty() ){ e = ss.top(); vec.push_back( *e ); ss.pop(); } for (int j = 0; j < vec.size(); ++j) { cout << vec[j].v() << " "; if( j == vec.size()-1 ) cout<
              
               <

s就是开始遍历的节点，首先起始点肯定是要被访问的，所以自然marked就是true了，代表被访问过，起始点的距离直接就是0，因为起始点是到自己没有路径。压进堆里面，如果堆不为空，遍历最小边的原点，这个时候就是属于松弛的过程了，看看有没有过当前最小的节点可以得到更小的边，如果有，那么看看当前堆里面有没有包含了节点的最小路径，包含了就替换。

Bellman-Ford算法

上面提到的Dijskra算法是不可以处理负权边的，因为每一次找到最小的权值就判定它就是最短路径中的一条了，从已经的最小的路径再做松弛操作，也就是绕回来只能更大。但是如果是存在了负权边：

很明显，这个时候再绕回来就比原来的要短了，这个时候最短的就不一定是最小的了。这个时候发现绕道走是最快的，这仍然是一个松弛操作，所以处理这种负权边依然离不开松弛操作。还有一种特殊情况：

这个时候2到0也有一个更小的负权值，这种环就叫做负权环，因为每循环一下权值就更小，第一次可能是2就到了2这个节点，然后发现从1到更快，而再绕一圈权值反而更小。所以有负权环的图是没有最短路径的，然而这个图其实也是没有最短路径的，因为只要到达了1或者2这两个顶点就会在这两个顶点之间不断循环，因为负权边是大于正权边的，来回有肯定更小。

Bellman-Ford算法的前提就是不能有负权环，但是这个前提不是一定的条件，因为运行的时候是可以知道有没有负权环，如果有那么是出不来结果的。算法复杂度

O(EV)

。处理的问题越多，那么复杂度就越大。同时如果存在的顶点经过了两次，那么就存在负权边。从一个顶点到另一个顶点最多只要经过v个顶点，有v01条边，如果违反了那么就证明是有负权环。一开始的思路其实差不多的，但是并不是只是找到最短的一条就停止，松弛操作的本质是绕道看看是不是更小的，所以自然的，遍历所有的点，看看是不是更小。

对一个点的一次松弛操作，就是找到经过这个点的另外一条路径，多一条边权值更小。如果一个图没有负权环，从一个点到另外一个点的最短路径，最多经过所有的v个顶点，有v-1条边，所以就是对所有的点进行v-1词松弛操作。事实上对所有的点进行v-1次松弛操作理论上就找到了从源点到其它所有点的最短路径。如果还可以进行松弛，那么就证明是有负权边了。

实现起来其实很简单：

namespace Ford{    template 
     
          class BellmanFord{    private:        Graph &G;        int s;        Weight* distTo;        vector
      
       
        *> from;        bool hasNegativeCycle;    public:        bool detectNegativeCycle(){            for (int i = 0; i < G.V(); ++i) {                typename Graph::adjIterator adj(G, i);                for (auto e = adj.begin(); !adj.end() ; e = adj.next()) {                    if (!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]){                        return true;                    }                }            }            return false;        }        BellmanFord(Graph &graph, int s):G(graph){            this->s = s;            distTo = new Weight[G.V()];            for (int i = 0; i < G.V(); ++i) {                from.push_back(NULL);            }            distTo[s] = Weight();            for (int pass = 1; pass < G.V(); ++pass) {                for (int i = 0; i < G.V(); ++i) {                    typename Graph::adjIterator adj(G, i);                    for (auto e = adj.begin(); !adj.end() ; e = adj.next()) {                        if (!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]){                            distTo[e->w()] = distTo[e->v()] + e->wt();                            from[e->w()] = e;                        }                    }                }            }            hasNegativeCycle = detectNegativeCycle();        }        void show(){            stack
        
         
           *> ss;            for (int i = 1; i < G.V(); ++i) {                vector
          
           
            > vec; cout << i << " :" << endl; Edge
            
              * e = from[i]; while (e->v() != this->s){ ss.push(e); e = from[e->v()]; } ss.push(e); while( !ss.empty() ){ e = ss.top(); vec.push_back( *e ); ss.pop(); } for (int j = 0; j < vec.size(); ++j) { cout << vec[j].v() << " "; if( j == vec.size()-1 ) cout<
             
              <

做完V-1次松弛操作之后，再做一次看看能不能找到更小的，如果还可以，那么就证明是有环了。

最后附上github地址：