最短路径问题

0x00 什么是最短路径

​ 在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。

这条路径就是两点之间的最短路径（shortest path），第一个顶点为源点（source）最后一个顶点为终点（destination）

​ 1单源最短路径问题 从固定源点出发，求其到所有其他顶点的最短路径

​ 又分为 无权图 和 有权图 （有向无向不影响）

​ 2多源最短路径问题 求任意两顶点间的最短路径

理论上我们学会了求单源最短路径问题后，那么可以对多源路径中，每一个对源点–>到顶点都用一遍单源最短路径算法，但实际上，在某种情况下，我们有更聪明 更好的算法

0x01 无权图的单源最短路径问题求解

​ 按照递增（非递减）的顺序找到各个顶点的最短路径

​ 无权图的单源最短路径问题和bfs类似，bfs每一层，即是往前走一步

​ 其时间复杂度和bfs一样 用邻接表时为O（v+e） 用邻接矩阵时为O（v^2） 其中v为vertex定点数，e为edge，边数。伪代码实现

void Unweighted(vertex s){
  	enqueue(s,q);
    while(!isempty(q)){
        v=dequeue(q);
        for(v的每个邻接点w){
            if(dist(w)==-1){//一开始初始化dist数组全为-1，如果-1则未访问
                dist[w]=dist[v]+1;//跟新dist[w]为对应距离
                path[w]=v;//用静态链表记录每个节点的父节点，到时候要查找路径直接不断读取对应父节点
                enqueue(w,q);
            }
        }
    }
}

0x02 有权图的单源最短路径问题求解

​ 不能有负值圈（即某个回路的权值为负值）

​ 一样的 按照递增（非递减）的顺序找到各个顶点的最短路径

​ dijkstra算法

​

​ 关于1 用反证法，如果从s->v 的最短路径 还要经过vi以外的顶点w，那么s->v最短=s->w最短+w->v最短也就是s->w最短 比 s->v最短小，但是我们是按照 最短距离 递增收录的，所以w必然在v之前已经被收录了，所以w必定在vi里与假设矛盾

​ 关于3 我们增加一个v的时候，如果有与v直接相连的w，那么到w的最短路径就有可能从v经过了（因为v刚刚被收录的），而w必然是没有被收录的，因为w还会被改变dist，所以不在vi里面

​ 伪代码实现

void weighted(vertex s){
    while(1){
        v=未收录顶点中的最小；
        if（v）{
            collected[v]=true;
            for(v的每个邻接点w){
                if(collected[w]==false){
                if(dist[v]+E<v,w><dist[w]){//由于该不等式在，所以dist初始化为正无穷
                    dist[w]=dist[v]+E<v,w>;
                    path[w]=v;
                }
                }
            }   
        }else{
            break;
        }
    }
}

该算法时间复杂度分析

​

​ 根据如何找到未收录的最小值，时间复杂度有两种，该算法会确保所有顶点都被收录，因此while 执行的次数是顶点数v，对于单向图，for被执行的总次数是边数e（无向图也是e，因为有个if判断是不是已经被收录了，所以一条边对应一次for）

​ 所以根据找到最小值的方法，分为遍历法和最小堆法，遍历法每次while会执行一次遍历，for循环里只有一个简单的赋值，因此 为v^2+e ，而最小堆则while时弹出一个节点，logv，在for里要跟新一个节点数据，也为logv 所以为图中的 vlogv + elogv