图的用法总结,包括图的表示方法，单源最短路径，任意两点间的最短距离和最小生成树

图中的乐趣

图的表示方法

图的表示方法有邻接矩阵和邻接表的方法

最小生成树

介绍最小生成树的一篇好文章http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html

单源最短路径

Bellman-Ford算法

Bellman-Ford算法的流程如下：

给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为INF, Distant[s]为0；
以下操作循环执行至多n-1次，n为顶点数：
对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；
若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；
为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在$Distant[u] + w(u, v) < Distant[v]$
的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。
可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).

算法的步骤为

第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
第二，进行循环，循环下标为从1到V-1（V等于图中顶点的个数）。在循环内部，遍历所有的边，进行松弛计算。
第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况（负圈）：
d（v） > d (u) + w(u,v)，则返回false，表示途中存在从源点可达的权为负的回路。

int cost[MAX_V][MAX_V];   //cost[u][v]表示边e=(u,v)的权值
int d[MAX_V];             //顶点s出发的距离
bool used[MAX_V];         //已经使用过的图
int V;                    //顶点数

void Dijkstra(int s){ 
        fill(d, d+V, MAX_INT);
        fill(used, used + V, false);
        d[s] = 0;

        while(true){
                int v = -1;

                //找出距离最小的没有访问过的节点
                for(int u = 0; u < V; u++){
                        if (!used[u] && (v == -1 || d[u] < d[v]))
                                v = u;
                }

                if (v == -1)  break;
                used[v] = true;
                //根据找出的节点更新剩余的节点的距离
                for (int u = 0; u < V; u++){
                        d[u] = min(d[u], d[v] + cost[v][u]);
                }
        }
}

struct edge {int from, to, cost};

edge es[MAX_E];   //边
int d[MAX_V];
int V, E;    //顶点数，边数

void shortest_path(int s){
        for(int i = 0; i < V; i++) d[i] = INF;
        d[s] = 0;
        while(true){
                bool update = false;
                for (int i = 0; i < E; i++){
                        edge e = es[i];
                        if (d[e.from] != INF && d[e.to]>d[e.from]+e.cost){
                                d[e.to] = d[e.from] + e.cost;
                                update = true;
                        }
                }
                if (!update) break;
        }
}

bool find_negative_loop(){
        memset(d, 0, sizeof(d));
        for(int i = 0; i < V; i++){
                for (int j = 0; j < E; j++){
                        edge e = es[j];
                        if (d[e.to] > d[e.from] + e.cost){
                                d[e.to] = d[e.from] + e.cost;
                                //如果第n次仍然更新，则存在负圈
                                if (i == V-1) return true;
                        }
                }
        }
        return false;
}

参考文章 http://www.acmerblog.com/bellman-ford-algorithm-5828.html

Dijkstra算法

参考文章为 http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html
Dijkstra算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止(类似于用红墨水浸透线绳)。注意该算法要求图中不存在负权边。

1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

2)算法步骤：
a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则正常有权值，若u不是v的出边邻接点，则权值为∞。
b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。

#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> P;   //第一个表示从源点出发距离，第二个表示所到节点

int V;   //顶点数
//图的表示方法
struct edge{int to, cost};
vector<edge> G[MAX_V];
//从源点到各顶点的距离
int d[MAX_V]；

void Dijkstra(int s){
    priority_queue<P, vector<P>, greater<P> > p_que;
    fill(d, d + V, MAX_INT); 
    d[s] = 0;
    p_que.push(P(0, s));
    
    while(!p_que.empty()){
        P p = p_que.top();p_que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;   
        for (int i = 0; i < G[v].size(); i++){
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] +e.cost;
                p_que.push(P(d[e.to], e.to));
            }
        }
    }
}