本文主要是介绍图论 *最短路*，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

多源最短路：Floyd

所谓多源，就是求图中任意两点的最短路。

floyd是一种动态规划的做法。

首先我们给出状态定义：$f(i,j,k)$ 表示除了点$i j$外，只经过$1~k$个点， $i$到$j$的最短路，不难得出状态转移方程：$ f(i,j,k) = min(f(i,k,k-1)+f(k,j,k-1)) $

优化掉$k$那一维之后就变成 ： $f(i,j) = min(f(i,k) + f(k,j))$ 。该算法处理图的边权，可正可负，复杂度 $O(n^3)$。

for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                f[i][j] = min(f[i][j],f[i][k] + f[k][j]);
//初始化f[i][j]即为两点边权，否则为正无穷

单源最短路

就是求从给定点到其余点的最短路

Dijkstra

该算法需要一个$dis$数组，$dis[u]$代表从点$u$到起点的最短路。

初始时，起点dis值为0，其余都为正无穷。

每次取出dis最小的点并删除，遍历他的所有出边进行松弛操作，直至全部结束。

取dis的过程可以用堆，也就是STL里的priority_queue来实现，总复杂度$O(nlog(n+m))$ 。

松弛操作：对于一个点v和一个点u,若dis[v] > dis[u] + w[u][v] 则dis[v]更新为dis[u] + w[u][v] ,可以形象的想象一个图，原来的dis中点v从原点x过来经过一条路径，现在变为从x到u再到v，路径更短，但看起来像绳子更松的样子，这也是为什么叫作松弛操作。

PS：Dijkstra只能用在非负权图，负权图得SPFA！！！

struct qwq{
    int u,dis;
    bool operator <(qwq a)const{return dis > a,dis;}//STL默认大根堆，这样改成小根堆，也就是先出小的 
};
inline void dijkstra(){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    priority_queue<qwq> q;
    dis[start] = 0;
    q.push((qwq){start,0});
    while(!q.empty()){
        int u.q.top();q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i=head[u];i;i=nxt[i]){
            int v = to[i];
            if(dis[v] > dis[u] + w[i]){
                dis[v] = dis[u] + w[i];
                q.push((qwq){dis[v],v});
            }
        }
    }
}

SPFA

首先关于这个算法有一句话不得不说——————————它 ！死 ！了 ！

但是呢，又没完全死，因为在构造数据下它太容易被卡掉，但是有的时候我们写不出正解，所以它反而又是我们不得不用的。

 首先他的复杂度，点数为N，边数为M， 期望复杂度$O(M) $ 但最坏复杂度$O(NM)$ 所以能用dijkstra 就别用SPFA 反复鞭尸

我们同样维护一个$dis$ ，只不过这回用队列来实现。

首先放入起点

每次取出队首元素，访问所有出边，进行松弛操作，如果连接的点没有入过队，将它入队。

直到队空

inline void spfa(){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[start] = 0;
    vis[start] = 1;
    queue<int>q;
    q.push(start);
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i=head[u];i;i=nxt[i]){
            int v = to[i];
            if(dis[v] > dis[u] + w[i]){
                dis[v] = dis[u] + w[i];
                if(!vis[v])q.push(v),vis[v] = 1;
            }
        }
    }
}

这篇关于图论 *最短路*的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！