Dijkstra

LW417 · 2018-10-17 19:25:20 · 个人记录

#include<iostream>
#include<cstring>
#define INF 9999999
using namespace std;
int t,c,ts,te;
int dis[250001]={0};//dis[i]表示从出发点到点i的最短距离
bool visit[250001]={0};
int f[25001][25001]={0};
void dijkstra()
{
    cin>>t>>c>>ts>>te;
    memset(f,INF,sizeof(f));//初始化最大值
    for(int i=1;i<=c;i++)
    {
        int from,to,d;
        cin>>from>>to>>d;
        f[from][to]=f[to][from]=d;
    }
    for(int i=1;i<=t;i++)
    {
        dis[i]=f[ts][i];
    }
    visit[ts]=true;//算法开始
    dis[ts]=0;
    for(int i=1;i<t;i++)
    {
        int minl=INF;
        int k=0;
        for(int j=1;j<=t;j++)//查找可以更新的点
        {
            if(!visit[j]&&dis[j]<minl)
            {
                minl=dis[j];
                k=j;
            }
        }
        if(k==0)
        {
            break;
        }
        visit[k]=true;
        for(int j=1;j<=t;j++)
        {
            if(dis[k]+f[k][j]<dis[j])
            {
                dis[j]=dis[k]+f[k][j];//松弛
            }
        }
    }
    cout<<dis[te];
}
int main()
{
    dijkstra();
    return 0;
}

以下为堆优化，用于顶点个数大的数据。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,X,Y,Z;
int dis[100010];
struct Edge{
    int v,w,nxt;
}edge[500010];
int head[100010],cnt=0;
void addEdge(int u,int v,int w)
{
    edge[++cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
struct node{
    int u,d;
    bool operator <(const node& rhs) const { //重载运算符
        return d>rhs.d;//<返回类型说明符> operator <运算符符号> （参数表）{<函数体>} 
    }
};
void Dijkstra()
{
    for (int i=1;i<=n;i++) dis[i]=2147483647;
    dis[1]=0;//如果要求起点为s，那改为dis[s]=0;
    priority_queue<node> Q;
    node a={1,0};//改为（s，0）；
    Q.push(a);
    while (!Q.empty()) {
        node fr=Q.top(); Q.pop();
        int u=fr.u,d=fr.d;
        if (d!=dis[u]) continue;
        for (int i=head[u];i;i=edge[i].nxt) {
            int v=edge[i].v,w=edge[i].w;
            if (dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w;
                Q.push((node){v,dis[v]});
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) {
        scanf("%d%d%d",&X,&Y,&Z);
        addEdge(X,Y,Z);
        //如果是无向图加双向边addEdge(Y,X,Z);
    }
    Dijkstra();
    for (int i=1;i<=n;i++) printf("%d ",dis[i]);
    return 0;
}