2020-08-05_迪斯科算法

今天也没有干多少事，主要复习了一下dijkstra算法。、
迪斯科算法原理是找每次与源头距离最近的点，利用该点进行松弛操作，直到所有的点都取一遍

//时间复杂度 N^2
while(num!=n)
{
    int minn=0x3f3f3f3f,k;
    for(int i=1; i<=n; i++)
    {
        if(dis[i]>minn&&!vis[i])
        {
            dis[i]=minn;
            k=i;
        }
        vis[k]=1;
        num++;
        for(int i=1; i<=n; i++)
            if(!vis[i]&&dis[i]>dis[k]+d[k][i])
                dis[i]=dis[i],dis[k]+d[k][i];
    }
}
//时间复杂度为 (V+E)lg(V) 差不多为n lg的底数不是10只是缩写
queue<pair<int,int>,greater<pair<int,int>>>q;
q.push(1,0);
while(!q.empty)
{
    pair<int,int>k=q.top();
    q.pop();
    if(vis[k.second])
        continue;
    vis[k.second]=1;
    for(int i=1; i<=n; i++)
        if(dis[i]>dis[k.second]+d[k.second][i]])
        {
            dis[i]=dis[k.second]+d[k.second];
            q.push(pair<int,int>(dis[i],i));
        }
}
//另一种
priority_queue<pair<int,int> >q;
void dijkstra(int start)
{
    memset(dist,0x3f,sizeof(dist));
    memset(v,0,sizeof(v));
    dist[start]=0;
    q.push(make_pair(0,start));
    while(!q.empty())
    {
        while(!q.empty() && (-q.top().first)>dist[q.top().second])//如果大于已更新数据说明该点已访问过
            q.pop();
        if(!q.empty())
            return;
        int x=q.top().second;
        q.pop();
        for(int i=head[x];i;i=nxt[i])
        {
            int y=to[i];
            if(dist[y]>dist[x]+val[i])
            {
                dist[y]=dist[x]+val[i];
                q.push(make_pair(-dist[y],y));
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62