最短路问题讲真的是真的不难,只要熟悉了算法思想,加上代码能力提高就完全可以的。

简述:
1.如果是稀疏图用邻接表,稠密图用邻接矩阵.
2.单源无负权优先用堆优化Dijkstra.
3.单源有负权优先用SPFA.
4.多源,真的很多的话,用Floyd.

5.规定走的步数的只能用原版Bellman_ford算法.

单源最短路


Dijkstra

[heimu]Dijkstra算法呢,快是真的快,毕竟实Dijkstra花5分钟在理发店想出的。[/heimu]
然后呢,他有一个问题,不能处理非实际问题,就是说不能处理负权

算法思路

首先我们要明确只是一个贪心算法。简单说就是懒。
算法的核心是一个dist数组,他存储着根节点u到各个点的最短路径。
我们还需要明确在最短路中重边和自环的处理:
1.邻接表中我们必须要对他进行处理,因为最短路的性质决定了他会帮我们处理。
2.邻接矩阵中我们要对Gi取一个最小值。因为我们将初始化Gi为0所以我们不需要额外处理自环。
那么开始算法过程:
1.初始化:因为根节点u到自己的距离为0,所以初始化dist[]除了u以为的元素为INF(+∞),u定义为0.还需要存储一个st[]表示我们是否一定确定这个点的了。并且st[u]=true;
2.遍历u可以到达的所有的边,更新dist数组。
3.查找dist数组中没有在st[]中确定的点中路径最短的点。更新st[]中这个点为true;
4.重复以上步骤;

Dijkstra_simple_code

//适合稠密图幺,这里用邻接矩阵。
const int N 100010;
const int INF 0x3f;
bool st[N];
int dist[N];
int G[N][N];
int dijkstra(int u){
    memset(dist, 0x3f, sizeof dist);
    dist[u]=0;
    For(i,1,n-1){
        int t = -1;
        For(j,1,n){if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;}
        st[j]=true;
        For(j,1,n){dist[j]=min(dist[j],dist[t]+G[t][j]);}
    }
    return dist[m]==INF?-1:dist[N];
}

Dijkstra_heapgood_code

//适合稀疏图幺,这里用邻接表
#define PII pair<int,int>
const int N 100010;
const int INF 0x3f3f3f3f;
int h[N],ne[N],e[N],w[N],idx;
bool st[N];int dist[N];
priority_queue<PII,vector<PII>,greater<PII>> q;
int dijkstra(int u){
    memset(dist,0x3f,sizeof dist);
    memset(h,-1,sizeof h);
    dist[u]=0;q.push({dist[u],u});
    while(!q.empty()){
        PII t = q.top();q.pop();
        int ver = t.second, dis=t.first;
        if(st[ver])continue;
        st[ver]=true;
        for(int i = h[ver];i!=-1;i=ne[i]){
            int j = e[i];
            if(dist[j]>dis+w[i]){
                dist[j]=dis+w[i];
                q.push({dist[j],j});
            }
        }
    }
    return dist[n]==INF?-1:dist[n];
}

emm,个人推荐第二种堆优化的,好思考,而且快,没错是王道。

bellman_ford

bellman_ford真的很man,他是需要n次遍历m条边,当然这是朴素版。
然后堆优化版就好多了,堆优化的你也可以叫他SPFA,没错他死了。
话虽这么说,但是,他有Dijkstra无法替代的地方,就是它可以判断负环。可以处理负权路径。还行吧

算法思路

初始化:dist[]数组初始化为+∞,定义最傻的起点、边、中点、权值的结构体数组。dist[u]初始化为0。
1.遍历所有的边,更新以中点为下标的dist[]的值
2.1重复n次。
ps:因为这里会处理负权,所以呢,dist[i]的值只要大于INF/2就可以。

bellman_ford_simple

struct Edge{
    int a,b,w;
};
Edge e[N];int dist[N];
int bellman_ford(int u){
    memset(dist,0x3f,sizeof dist);
    dist[u]=0;
    For(i,1,n){
        For(j,1,n){
            int a = e[j].a,b = e[j].b,w=e[j].w;
            dist[b]=min(dist[b],dist[a]+w);
        }
    }
    return dist[m]>INF/2?-1:dist[m];
}

bellman_ford_simple_limit

ps:这个算法是bellman_ford的衍生版,用来求走k步可以的最短路径问题,当k>=n&&不存在负权是他和bellman_ford_simple是一样的。

struct Edge{
    int a,b,w;
};
Edge e[N];
int dist[N];int backup[N];
int bellman_ford_simple_limit(int u){
    memcpy(backup,dist,sizeof dist);
    dist[u]=0;
    For(i,1,k){
        For(j,1,n){
                int a = e[j].a,b=e[j].b,w=e[j].w;
                dist[b]=min(dist[b]+backup[a]+w);
        }
    }
    return dist[m]>INF/2?-1:dist[m];//可能存在一种情况,就是其实这个点没有到达,但是他因为负权被更新变小了。
}

SPFA

int h[N],ne[N],e[N],w[N],idx;
int dist[N];bool st[N];
queue<int> q;
int spfa(int u){
    memset(dist,0x3f,sizeof dist);
    dist[u]=0;
    q.push(u);
    st[u]=true;
    while(!q.empty()){
        int t = q.front();
        q.pop();
        st[t]=false;
        for(int i = h[t];i!=-1;i=ne[i]){
            int j = e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return dist[j]==INF?-1:dist[j];//因为spfa只有更新的点才会继续往下更新,所以不需要考虑比INF小的情况。
}

SPFA_judge_Negative_loop

//ps:根据判断负环和判断从u开始的负环的意义,初始化是不一样的。
int h[N],ne[N],e[N],w[N],idx;
int dist[N];bool st[N];
int cnt[N];
queue<int> q;
bool spfa(int u){
    For(i,1,n){
        q.push(i);
        st[i]=true;
    }
    while(!q.empty()){
        int t = q.front();
        q.pop();
        st[t]=false;
        for(int i = h[t];i!=-1;i=ne[i]){
            int j = e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n)return true;
                if(!st[j]){ 
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
   return false;
}

多源最短路


Floyd

写起来感觉不像最短路,提交上去超时感人。。,多源问题那种很多很多多到调用n次Dijkstra都很慢时,用它吧。代码很短。速度很慢。
当然Floyd可以处理负权路径,但是不能处理和判断负权回路

算法思路

怎么说呢就是DP,无话可说.

Floyd_code

void floyd(){
    For(k,1,n)
        For(i,1,n)
            For(j,1,n)
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}

觉得好,就转发吧(づ ̄3 ̄)づ╭❤~。

name.com购买域名廉价稳定无需备案 年付.xyz.site.life$3点击购买赠送5$优惠券
racknerd购买无需备案CN2服务器,速度高速稳定节日优惠力度强 节日会推出各种优惠套餐【点击注册】目前推出3H2.5G40GB6T每年$27.80两年$55.60套餐【快来注册
Last modification:April 7th, 2020 at 11:22 am
觉得好的话就评论,转发,投币。