2017-01-22

最短路问题(Bellman/Dijkstra/Floyd)

寒假了，继续学习停滞了许久的算法。接着从图论开始看起，之前觉得超级难的最短路问题，经过两天的苦读，终于算是有所收获。把自己的理解记录下来，可以加深印象，并且以后再忘了的时候可以再看。
最短路问题在程序竞赛中是经常出现的内容，解决单源最短路经问题的有bellman-ford和dijkstra两种算法，其中，dijikstra算法是对bellman的改进。解决任意两点间的最短路有Floyd-warshall算法。

单源最短路1(bellman-ford)

单源最短路是从一个点出发，到其他所有顶点的最短距离。起点是s，假如求s到顶点i的最短路(用数组d[i]表示s到i的最短距离,d[s]=0,d[i]=INF)，会有这样一个关系式：
d[i]=min[ d[j]+cost(从j到i的距离),e=(j,i)∈E} ] 即等于（s到j的最短距离加上j到i的距离）中的最小的，j是与i相连的顶点。
先反着想，想要求到i的就得求到j的，同样想要求到j的短距离，就得求与j相连的点的。这样追根溯源到s上，会发现此时d[s]是确定的，s到与其相连的顶点的距离也是确定的，原来还是得正着计算啊。
从s出发，因为两个值都是可以确定的，所以第一次执行那个式子后，与s相连的点的值都会被更新，并且会确定一个与s相连的点的最短路，再继续执行那个式子，又会确定一个（每次执行都要一个循环把所有的点试一遍，因为这样才能适用以任何一个点作为起点的情况），下面是代码：

#define INF 0x3f3f3f3f
struct edge{int from,to,cost;};
edge ee[max_e];//存储每条边的信息
int d[max_v];//表示s到每个顶点的最短距离
int v,e;//顶点数和边数
void bellman(int s){
    memset(d,INF,sizeof(d));
    d[s]=0;
    while(true){
        bool update=false;
        for(int i=0;i<e;i++){
            edge et=ee[i];
            if(d[et.from]!=INF&&d[et.to]>d[et.from]+et.cost){
                d[et.to]=d[et.from]+et.cost;
                update=true;
            }
        }
        if(!update) break;//如果不再进行更新就退出
    }
}

然后在挑战程序设计竞赛上，又专门写了一个函数来判断是否有负圈，下面是代码：

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

因为如果不存在负圈，只需要循环v-1次就行了，所以在第一个代码的基础上稍微改动一下就行，只需要添加一个计数器。
这是最终版代码：

#define INF 0x3f3f3f3f
struct edge{int from,to,cost;};
edge ee[max_e];//存储每条边的信息
int d[max_v];//表示s到每个顶点的最短距离
int v,e;//顶点数和边数，双向的边数要*2；
//返回true计算最短路成功，返回false存在负圈；
bool bellman(int s){
    memset(d,INF,sizeof(d));//赋最大值的技巧
    d[s]=0;
    int j=0;//添加的计数器
    while(true){
        bool update=false;
        for(int i=0;i<e;i++){
            edge et=ee[i];
            if(d[et.from]!=INF&&d[et.to]>d[et.from]+et.cost){
                d[et.to]=d[et.from]+et.cost;
                update=true;
            }
        }
        j++;
        if(!update) return true;
        if(j==v) return false;//当进行第v次循环时，说明存在负圈
    }
}

这里给赋值无穷大有个小技巧。这是针对于有向图来说的，如果是无向图，自己把from和to交换后再输入一次就好。

单源最短路2(dijkstra)

迪杰斯特拉算法对bellman进行了修改，在bellman中，刚开始是到s的最短距离是0，是确定的，然后下一次循环会确定与其相连的顶点里面距离最小的那个，这样每次都会从已经确定了最短路的顶点里面往外扩散。dijkstra就是把每次确定了的顶点给记录下来，然后每次都从未确定的顶点里面找出最短距离最小的那个，然后用它对其相邻的顶点进行更新。先采用邻接矩阵的方式来实现，下面是代码：

int d[max_v];//表示s到每个顶点的最短距离
int v,e;//顶点数和边数
int g[max_v][max_v];// ！初值全部为INF
bool used[max_v];//标记已经更新过的顶点
void dijkstra(int s){
    fill(d,d+v,INF);
    fill(used,used+v,false);//false表示未更新的。
    d[s]=0;
    while(true){
        int t=-1;
        for(int i=0;i<v;i++){//查找出最短距离最小的那个点
            if(!used[i]&&(t==-1||d[t]>d[i])) t=i;
        }
        if(t==-1) break;//如果未查找到说明所有的点都已经确定;
        used[t]=true;//将确定了的点记录下来;
        for(int i=0;i<v;i++){
            d[i]=min(d[i],d[t]+g[t][i]);
        }
    }
}

你可能会发现每次查找最小距离的顶点的时候，是对所有的点进行的查找，在这里可以进行优化，可以用堆来进行优化，我们可以用stl中的priority_queue来实现。你可能还会发现在用最短距离已经确定了的点来对其相邻的点进行更新的时候，可以用邻接表来优化（邻接表记录着每个顶点与哪些顶点相连。）。下面是代码:

struct edge{int to,cost;};
typedef pair<int,int> P;//first是最短距离，second是顶点编号
vector<edge> g[max_v];
int d[max_v];//表示s到每个顶点的最短距离
int v,e;//顶点数和边数
void dijkstra(int s){
    priority_queue<P,vector<P>,greater<P> > que;
    fill(d,d+v,INF);
    d[s]=0;
    que.push(P(0,s));
    while(!que.empty()){
        P p=que.top();
        que.pop();
        int vt=p.second;
        for(int i=0;i<g[vt].size();i++){
            edge e=g[vt][i];
            if(d[e.to]>d[vt]+e.cost){
                d[e.to]=d[vt]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}

任意两点间的最短路(floyd-warshall)

floyd是用动态规划的思想来解决问题，用一个数组d[i][j]来表示从i到j的最短距离。在顶点i和j之间可能会是顶点k，如果用0-v-1来表示每个顶点会有这样一个关系式： d[i][j]=min(d[i][j],d[i][k]+d[k][j] ) 然后对所有的顶点k都计算一遍。下面是代码：

int d[max_v][max_v];//不存在时设为INF，注意d[i][i]=0;
int v;//顶点数
for(int k=0;k<v;k++){
    for(int i=0;i<v;i++){
        for(int j=0;j<v;j++){
            d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        }
    }
}

floyd跟bellman一样，都可以处理边为负数的情况，只需要判断d[i][i]为负数的即可。

路径记录

有的问题需要输出最短路径，以dijkstra算法为例，当d[j]=d[k]+cost[k][j]时候，顶点k便是顶点j的前驱，我们只需在更新的时候进行记录就行了。

int prev[max_v];// ***添加这一个数组
int d[max_v];//表示s到每个顶点的最短距离
int v,e;//顶点数和边数
int g[max_v][max_v];// ！初值全部为INF
bool used[max_v];//标记已经更新过的顶点
void dijkstra(int s){
    fill(d,d+v,INF);
    fill(used,used+v,false);//false表示未更新的。
    d[s]=0;
    while(true){
        int t=-1;
        for(int i=0;i<v;i++){//查找出最短距离最小的那个点
            if(!used[i]&&(t==-1||d[t]>d[i])) t=i;
        }
        if(t==-1) break;//如果未查找到说明所有的点都已经确定;
        used[t]=true;//将确定了的点记录下来;
        for(int i=0;i<v;i++){
            //d[i]=min(d[i],d[t]+g[t][i]);
            if(d[i]>d[t]+g[t][i]) prev[i]=t;//***新增
        }
    }
}
//到t的最短路求解
vector<int> get_path(int t){
    vector<int> path;
    for( ;t!=-1;t=prev[t]) path.push_back(t);
    reverse(path.begin(),path.end());
    return path;
}

经过阅读发现《挑战程序设计竞赛》中的算法描述还是比较准确易懂的，代码实现也非常简洁。
理解是一回事，会运用又是一回事。结果我又花了两天才写完这篇文章并把代码实现出来。自己在写的时候，总是感觉很多东西有点模棱两可，不知道该怎么解释，这应该就是理解不够深刻的原因吧。如果很清楚其中的过程，就不会有这种感觉了。
自己写的可能有很多错误的地方或需要改进的地方，如有发现，欢迎指正！
最短路算法还有A*算法，对bellman进行优化的SPFA算法，以后学习了再来更新。

转载请注明出处：http://taowusheng.cn/
微博：寒枫–0-0–
知乎：https://www.zhihu.com/people/tao-wu-sheng
豆瓣：YIFEI