Java教程

图论 *最短路*

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

多源最短路: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;
            }
        }
    }
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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