最短路算法(dijsktra,floyd)

本文主要是介绍最短路算法(dijsktra,floyd)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

floyd，复杂度O(n^3)

void floyd(int s,int e)//start end
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(g[i][j]>g[i][k]+g[k][j])
                    g[i][j]=g[i][k]+g[k][j];
            }
        }
    }
    cout<<g[s][e]<<endl;
}

dijsktra( O(mlogm) )

struct Node{
    int to,dis;
};//携带边的终边，长度信息
vector<Node> g[maxn];
void add(int u,int v,int w)
{
    g[u].push_back({v,w});
}
int dis[maxn];//最短路数组
typedef pair<int,int> P;//将int,int型数据重命名为P
int dis[maxn];//最短路数组
typedef pair<int,int> P;//将int,int型数据重命名为P
void dij(int start){
    memset(dis,0x3f,sizeof(dis));//初始最短路为inf
    priority_queue<P,vector<P>,greater<P> > q;//小根堆，堆顶是最小值
    dis[start]=0;//起点自己距离为0
    q.push(P(0,start));//起点入队，注意pair数组第一个是距离，第二个是点号
    while(!q.empty()){
        P p=q.top(); q.pop();//取出堆顶
        int u=p.second;
        if(dis[u]<p.first)        continue;
        //祖传优化，同一点可能多次入队，如果答案更劣可以舍弃
        for(int i=0;i<edge[u].size();i++){//邻接表遍历
            int v=edge[u][i].to;
            if(dis[v]>dis[u]+edge[u][i].dis){//松弛
                dis[v]=dis[u]+edge[u][i].dis;//成功了就更新，入队
                q.push(P(dis[v],v));
            }
        }
    }
    return ;
}

这篇关于最短路算法(dijsktra,floyd)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！