最短路径-白红宇

最短路径

阅读量：6518 次

发布时间：2019-06-24

本文共 2519 字，大约阅读时间需要 8 分钟。

要说最短路，先来说说最长路，理解了最长路问题之后，才能透彻理解最短路的几个算法。

最大化问题在线性结构、树型结构里面可以轻松构造无后效性的最优子结构解决，但是在图结构里面就很麻烦，原因是顺着一个点推下去之后，图结构中还存在另一个点亦可到达此点，可能推翻前面存的结果。所以要对整个图进行Relax。

最短路径算法中，Dijkstra，Bellman-Ford，Floyd的Relax操作都使用了动态规划的思想，具体点就是著名的“三角形不等式”。

现在拿最短路的几个算法来求试试最长路问题，Dijkstra只是从根向儿子推了一遍，所以Dijkstra算法建立最优子结构无法求解最长路。

Bellman-Ford 暴力地把图中所有边松弛（Relax）V-1次，把所有的状态都用三角形不等式Relax了一遍，结果是对的，当然其中做了很多没必要的计算。

SPFA同上，只不过SPFA确立的一个Relax最大量的上界，对Bellman-Ford做了剪枝优化。

多源最长路是个NP-Hard问题，floyd无法求解。

另外Dijkstra还使用贪心的思想，导致贪负权路的结果是错的。

竞赛中，单源最短路径最偷懒的是Bellman-Ford优化过的SPFA方法，可以有效处理负权路/判断负环，甚至可以逆向求定源最长路，判断正环。

不过SPFA看图的结构，稀疏图平均复杂度低于O(n^2), 最差复杂度会退化渐进至O（VE) 。这时候就没有优先队列优化过的Dijkstra速度快了O(nlogn)。

所以没有负权还是乖乖Dijkstra吧，优先队列的优化一定得加上，O（n）和O（logn）的扩张线简直是天壤之别，

Tips：求最短路时，第一要注意是有向图还是无向图，第二就是初始化。存图推荐链式前向星，邻接表的话使用vector比较简洁（缺点是clear慢）。

三大模板。

1. SPFA

bool SPFA(){    queue
      
        Q;    memset(vis,0,sizeof(vis));    memset(cnt,0,sizeof(cnt));    for(int i=1;i<=n;i++) d[i]= (i==1?0:inf); // 最长路反过来    Q.push(1);　　cnt[1]++;　　while(!Q.empty())    {        int x=Q.front();Q.pop();        vis[x]=false;  //!        for(int i=0;i
       
        n) return true; //判断负环/正环                }            }        }}

View Code

2. 优先队列优化的Dijkstra（链式前向星版，这里要郑重推荐一下链式前向星，我在跑树链剖分的时候用vector邻接表跑了4s+,TLE了。但是用了链式前向星之后，只用了1.5s）

struct Edge{    int to,next,w;}edge[maxn*2];struct status{    int d,p;    status(int d,int p):d(d),p(p) {}    bool operator < (const status &a ) const {
    return d > a.d;}};int head[maxn],vis[maxn],d[maxn],n;void dijkstra(int s){    memset(vis,0,sizeof(vis));    priority_queue
      
        Q;    Q.push(status(0,s));    for(int i=1;i<=n;i++) d[i]=(i==s?0:inf);    while(!Q.empty())    {        status tt=Q.top();        Q.pop();        int x=tt.p;        if(vis[x]) continue;        vis[x]=true;        for(int i=head[x];i!=-1;i=edge[i].next)        {            if(d[x]+edge[i].w

View Code

3. Floyd（带上最小环）

void floyd(){    memset(G,1,sizeof(G));//1=inf    memset(d,1,sizeof(d));    for(int i=1;i<=n;i++) G[i][i]=G[i][i]=d[i][i]=d[i][i]=0;    int MIN=1<<28;    for(int i=1; i<=m; i++)    {        scanf("%d%d%d",&u,&v,&w);        G[u][v]=G[v][u]=d[u][v]=d[v][u]=w;  //无向图写法    }    for(int k=1; k<=n; k++)    {        for(int i=1; i
      
       =inf) printf("No solution.\n");//无最小环}

View Code

@练习题

hdu3790（双权最短路）

POJ1062（比较坑爹，自己百度题解）

POJ1125（单源里面最长的，多源里面最短的，orz）

POJ1860（逆向Bellman-Ford，判断正环）

POJ3259（背景是霍金的虫洞，挺有趣的题，意思比较难懂，前进是正权是无向图，后退是负权是有向图）

vijos1391（挺奇葩的题，Relax不再是累加路径，而是取最小值）。

转载于:https://www.cnblogs.com/neopenx/p/4004325.html

你可能感兴趣的文章