学习笔记4（最短路）

dijkstra:求单源最短路

算法步骤:
1. 找离起点x最近的未讨论过的点k。
2. 判断经过k点，起点x到其他点的距离是否缩短，如缩短
则更新。将k点标记为已讨论。
3. 重复进行第1步，直到所有点都被讨论过为止。

于是我们可以得出:

dis[i]=min{dis[k]+Map[k][i]}

1<=i<=n  k是未讨论过的，离起点最近的点

dis[i]表示从起点到i点最短距离

$PS$ :为了方便，此篇文章部分采用邻接矩阵存图，建议各位换成更高效的存图方法。

$code$ :

void dijkstra(int x){
    for(int i=1;i<=n;i++){        初始化
        mark[i]=false;         mark记录第i号节点是否被讨论过
        dis[i]=Map[x][i];     初始化dis数组，dis[i]用于记录起点x到i的最短距离
    }
    mark[x]=true;           将起点标记为已被讨论，防止走回头路
    do{                            算法核心部分：
        minn=inf;
        k=0;            k记录离x最近的点的编号
        for(int i=1;i<=n;i++)     寻找当前离x最近且未被讨论过的节点
            if((mark[i]==false) && (dis[i]<minn)){
                minn=dis[i];
                k=i;
            }
               讨论经过k点，有没有其他点到x的距离缩短
        if(k>0){
            mark[k]=true;将k号点设置为已被讨论过
            for(int i=1;i<=n;i++)若经过k号点，起点x到i的距离缩短，则更新dis[i]
                if(dis[i]>dis[k]+Map[k][i])
                    dis[i]=dis[k]+Map[k][i];
        }
    }while(k>0);
}

时间复杂度 $O(n^2)$ 这肯定不行，得想办法优化！

可以发现，每次我们都是要找出离x最近的点的编号，于是我们便可以用强大的stl里的优先队列来完成这个操作，将其优化至 $O(nlog_n)$

$code$ ：dij+堆优化+链式前向星

struct node{
    int num,dis;       num记录节点编号，dis记录起点到该店的最短距离
    bool operator < (const int &a) const{
        return dis>a.dis;    重载< 以dis从小到大排序 
    }
};
void dijkstra(int s){
    for(int i=1;i<=n;i++){初始化
        dis[i]=inf;
        mark[i]=false;
    }
    dis[s]=0;
    priority_queue<node> q;以距离为关键字的小根堆，方便取出目前离起点最近的点
    q.push((node){s,0});
    while(q.size()){
        int x=q.top().num;
        q.pop();
        if(mark[x])  若离起点最近的点x已被讨论过，就跳过
            continue;
        mark[x]=true;
        for(int i=Last[x];i;i=Next[i]){  链式前向星
            int y=End[i];
            if(!mark[y] && dis[y]>dis[x]+len[i]){更新dis[]
                dis[y]=dis[x]+len[i];
                q.push((node){y,dis[y]});
            }
        }
    }
}

SPFA (他死了)

SPFA是Bellman-Ford算法的一种队列实现，减少了不必要的运算。

算法流程：

用一个队列来进行维护。初始时将起点加入队列。每次从队列中取出一个元素，并对他所连接的点进行松弛，若某个点松弛成功（则通过那个点到起点距离缩短），则将其入队。直到队列为空

简单的说就是队列优化的bellman-ford，利用了每个点不会更新次数太多的特点

SPFA的时间复杂度是O(kE)，k一般取2左右（k是增长很快的
函数ackermann的反函数,2^65536次方也就5以下），可以处
理负边。

SPFA的实现甚至比Dijkstra或者 Bellman_Ford还要简单

queue<int> q;
void spfa(int s){    s为起点，求s到图中所有点的距离
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    q.push(s);
    mark[s]=true;
    dis[s]=0;
    while(q.size()){
        int x=q.front();
        q.pop();
        mark[x]=false;
        for(int i=1;i<=n;i++)   讨论与x相连的点
            if(dis[x]+Map[x][i]<dis[i]){  若x通过i点到起点的距离缩短则更新
                dis[i]=dis[x]+Map[x][i];
                if(mark[i]==false){    若不在队列中，入队
                    q.push(i);
                    makr[i]=true;
                }
            }
    }
}

那么，上文说了SPFA可以处理负权边，那么遇到了负环（负权回路）该怎么处理呢?

用SPFA判断负权回路

让我们来想一想：
在SPFA算法中，每个点最多进队多少次？

很显然是n-1次，因为对于一个点x，最坏情况下是其余n-1个点都可以将其松弛。

所以如果有一个点进队次数超过了n次，我们就可以认定，该图中存在负权回路，可以果断结束SPFA了。

$code$ :

queue<int> q;
int cnt[N]    用于统计每个节点进队次数 
void spfa(int s){
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    q.push(s);
    mark[s]=true;
    dis[s]=0;
    while(q.size()){
        int x=q.front();
        q.pop();
        mark[x]=false;
        for(int i=1;i<=n;i++)
            if(dis[x]+Map[x][i]<dis[i]){
                dis[i]=dis[x]+Map[x][i];
                if(mark[i]==false){
                    q.push(i);
                    cnt[i]++
                    if(cnt[i]==n){
                        cout<<"有负权回路";
                        return; 
                    }
                    makr[i]=true;
                }
            }
    }
}

floyd：计算每一对顶点的最短距离（其实跟dp差不多）

算法思想：
枚举图中每一个顶点k，判断图中其他节点间的距离在经过k后是否缩短，如果是，则用新的更短距离取代原距离

$code$ :

floyd的数学表达式：
f[i][j]=min{f[i][k]+f[k][j]}
1<=i,j,k<=n

for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(Map[i][j]>Map[i][k]+Map[k][j])
                Map[i][j]=Map[i][k]+Map[k][j];

$flyod$ 的时间复杂度为 $O(n^3)!!!!!$