算法拾遗 2018.11.26

经历过几次大大小小的比赛之后,感觉自己的状态总算是恢复了一些。

算法还是要继续复习。


碎片四 最短路径

用来求图上的最短路径。使用邻接表存图。

首先是曾经我最常使用的spfa算法,它实现起来要比堆优化的dij简单一些,原理是基于搜索。时间复杂度优秀,但是缺点非常明显,所以很容易被卡。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 5000015
#define INF 2147483647
#define ms(x) memset(x,0,sizeof(x));
using namespace std;
struct Edge{
    long long int from,to,dis;
};
Edge edge[maxn];
long long int n,m,s,u,v,d;
long long int head[maxn];
long long int dis[maxn];
bool inq[maxn];
long long int cnt = 0;
void add_edge(long long int from,long long int to,long long int dis){
    edge[++cnt].from = head[from];
    edge[cnt].to = to;
    edge[cnt].dis = dis;
    head[from] = cnt;
}

void spfa(void){
    queue<long long int> q;
    q.push(s);
    ms(inq);
    inq[s] = true;
    for (int i=1;i<=n;i++)
        dis[i] = INF;
    dis[s] = 0;
    while (!q.empty()){
        long long int u = q.front();
        q.pop();
        inq[s] = false;
        for (int i=head[u];i!=0;i=edge[i].from){
            long long int v = edge[i].to;
            long long int w = edge[i].dis;
            if (dis[u]+w < dis[v]){
                dis[v] = w+ dis[u];
                if (!inq[v]){
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }

}

int main(){
    cin >> n >> m >> s;
    for (int i=1;i<=m;i++){
        cin >> u >> v >> d;
        add_edge(u,v,d);
    }
    spfa();
    for (int i=1;i<=n;i++)
        cout << dis[i] << " ";
    return 0;
}

然后是dijkstra算法,它是一种基于贪心思想的算法。开始时设定两个集合,一个是已经更新了最短路径的点的集合,另一个就是还没有更新的。然后通过不断更新连接点的最短距离,最后一步一步地求出到达目标点的路径。

通过dijkstra,每一个节点都会产生若干(候选)最小距离。这些(候选)最小距离里面最小的才是真正的最小距离。
具体流程:
开一个数组,记录每个点当前属于哪一个阵营。
从堆中所有(候选)最小距离里面挑出一个最小的。如果node属于A阵营,说明之前已经遇到了一个node的(候选)最小距离,现在这个不是真的最小,跳过。
反之,检查所有node这个点的出边。假设出边指向v。如果v属于B阵营,那么我们将{v, dis[node]+w}加入堆中。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define ll long long 
#define INF 2147483647
using namespace std;
int n,m,s,head[50010],cnt;
ll dis[10010]; 
bool used[10010];
struct Edge{
    int to,from,dis;
}edge[500010];

void add_edge(int u,int v,int dis){
    edge[cnt].to=v;
    edge[cnt].from=head[u];
    edge[cnt].dis=dis;
    head[u]=cnt++;
}
typedef pair<int,int> P;
void dijkstra(int s){
    priority_queue<P,vector<P>,greater<P> > q;
    fill(dis,dis+n+1,INF);
    fill(used,used+n+1,false);
    dis[s]=0;
    q.push(P(0,s));
    while(!q.empty()){
        P p=q.top();q.pop();
        int u=p.second;
        if(used[u]) continue;
        used[u]=true;
        int pp=head[u];
        while(pp!=-1){
            int v=edge[pp].to;
            if(!used[v]&&dis[v]>dis[u]+edge[pp].dis){
                dis[v]=dis[u]+edge[pp].dis;
                q.push(P(dis[v],v));
            }
            pp=edge[pp].from;
        }
    }
}
int main(){
    memset(head,-1,sizeof(head));
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        add_edge(u,v,d);
    }
    dijkstra(s);
    for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
    return 0;
}

-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。