dijkstra

你的名字 2021-11-23 23:24 269阅读 0赞

Dijkstra算法适用于**边权为正**的无向和有向图，**不适用**于有**负边权**的图！！！

基本思想：  
  
1.将图上的初始点看作一个集合S，其它点看作另一个集合  
  
2.根据初始点，求出其它点到初始点的距离d\[i\] （若相邻，则d\[i\]为边权值；若不相邻，则d\[i\]为无限大）  
  
3.选取最小的d\[i\]（记为d\[x\]），并将此d\[i\]边对应的点（记为x）加入集合S  
  
（实际上，加入集合的这个点的d\[x\]值就是它到初始点的最短距离）  
  
4.再根据x，更新跟 x 相邻点 y 的d\[y\]值：d\[y\] = min\{ d\[y\], d\[x\] + 边权值w\[x\]\[y\] \}，因为可能把距离调小，所以这个更新操作叫做松弛操作。  
  
5.重复3，4两步，直到目标点也加入了集合，此时目标点所对应的d\[i\]即为最短路径长度。

![timg_image_quality_80_size_b9999_10000_sec_1534153565058_di_070f64924b7e584754a2693bf158f797_imgtype_0_src_http_3A_2F_2F5b0988e595225.cdn.sohucs.com_2Fimages_2F20171029_2Fa9ce9e515dfa4ddb86e9ccf3ebd96836.gif][]

如果利用堆来维护所有边中最小的值，那么复杂度会大大下降；

以下是优化后的代码

#include <iostream>
    #include <queue>
    #include <cstring>
    #define INF 2147483647
    using namespace std;
    struct littlestar
    {
        int to;
        int nxt;
        int w;
    }star[500010];
    int head[100010];
    int cnt=0;
    priority_queue<pair<int,int> > q; //第一位是dis值，第二位是点的编号  //优先队列可以模拟大根堆
    int d[100010],v[100010]; 
    void add(int u,int v,int o)
    {
        star[++cnt].to=v;
        star[cnt].w=o;
        star[cnt].nxt=head[u];
        head[u]=cnt;
    }
    void dijkstra(int u)
    {
        d[u]=0;
        q.push(make_pair(0,u)); 
        while(q.size())
        {
            int x=q.top().second;
            q.pop();
            if(v[x]) continue;
            v[x]=1;
            for(int i=head[x];i;i=star[i].nxt)
            {
                int y=star[i].to,z=star[i].w;
                if(d[y]>d[x]+z) d[y]=d[x]+z;
                q.push(make_pair(-d[y],y)); //存入dis值的相反数，把大根堆变为小根堆;
            }
        }
    }
    int main ()
    {
        int n,m,s,t;
        cin>>n>>m>>s>>t;
        for(int i=1;i<=n;i++) d[i]=INF;
        for(int i=1;i<=m;i++)
        {
            int u,v,o;
            cin>>u>>v>>o;
            add(u,v,o);
        }
        dijkstra(s);
        cout<<d[t];
    }

转载于:https://www.cnblogs.com/kamimxr/p/11213019.html

[timg_image_quality_80_size_b9999_10000_sec_1534153565058_di_070f64924b7e584754a2693bf158f797_imgtype_0_src_http_3A_2F_2F5b0988e595225.cdn.sohucs.com_2Fimages_2F20171029_2Fa9ce9e515dfa4ddb86e9ccf3ebd96836.gif]: https://timgsa.baidu.com/timg?image&quality=80&size=b9999_10000&sec=1534153565058&di=070f64924b7e584754a2693bf158f797&imgtype=0&src=http%3A%2F%2F5b0988e595225.cdn.sohucs.com%2Fimages%2F20171029%2Fa9ce9e515dfa4ddb86e9ccf3ebd96836.gif