yuzh的博客

❤ ECUST ❤

0%

单源最短路的链式前向星实现

发表于 更新于 Valine：

算法的原理以及邻接矩阵实现见先前写的单源最短路径。

相较于邻接矩阵，邻接矩阵在进行松弛操作时需要遍历每一条边，而基于链式前向星的实现仅需执行出度的个数次，大大节省了循环次数。

Dijkstra

下方算法中，dist记录了每个节点当前的最短路径，初始值设定为无穷大；flag记录了先前每一轮循环中未确定答案的点中路径最短的点，即已经获得答案的点；p记录了节点的直接前驱。

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
// Dijkstra
flag[1]=true;
dist[1]=0;
for(int i=head[1]; i!=-1; i=edge[i].next)
{
    dist[edge[i].to]=edge[i].weight;
    p[edge[i].to]=1;
}

for(int i=1;i<=n-1;i++)
{
    int temp=0x7f7f7f, t=1; // t为源点，此处设定为1 
    for(int j=1;j<=n;j++)
    {
        if(flag[j]==false && dist[j]<temp)
        {
            temp=dist[j];
            t=j;
        }
    }
    if(t==1) break; //无法到达任何一个点 
    flag[t]=true;
    for(int k=head[t]; k!=-1; k=edge[k].next)
    {
        int j=edge[k].to;
        if(flag[j]==false && dist[j]>dist[t]+edge[k].weight )
        {
            dist[j]=dist[t]+edge[k].weight;
            p[j]=t;
        }
    }
}

SPFA

此处实现中的pd用于判断是否存在负环，其余部分为标准SPFA。

判断负环的原理：判断入队次数是否>=n，如果是则说明有负环。

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
int dis[maxn], cnt[maxn];
bool inq[maxn], pd=false;
memset(dis, 0x3f3f3f3f, sizeof(dis));
memset(cnt, 0, sizeof(cnt));
memset(inq, false, sizeof(inq));
int n,m;
cin>>n>>m;
for(int i=1,u,v,w;i<=m;i++)
{
    cin>>u>>v>>w;
    if(w>=0)
    {
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    else
    {
        addEdge(u,v,w);
    }
}
queue<int> q;
q.push(1);
dis[1]=0;
inq[1]=true;
while(!q.empty())
{
    int cnthead=q.front(); q.pop(); inq[cnthead]=false;
    for(int i=head[cnthead];i!=-1;i=edge[i].next)
    {
        int to=edge[i].to, weight=edge[i].weight;
        if(dis[to]>dis[cnthead]+weight)
        {
            dis[to]=dis[cnthead]+weight;
            if(!inq[to])
            {
                if(++cnt[to]>=n)
                {
                    pd=true;
                    break;
                }
                inq[to]=true;
                q.push(to);
            }
        }
    }
    if(pd==true) break;
}
if(pd==true) cout<<"YES"<<endl;
else cout<<dis[n]<<endl;