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;
        }
    }
}

堆优化Dijkstra

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
63
64
65
66
67
68
69
70
// Djikstra + Priority_Queue
struct Node{
	int id;
	int dis;
	bool operator< (const Node &x)const
	{
		return x.dis<dis;
	}
};

int head[100010], cnt;
struct Edge{
	int to, weight, next;
}edge[200010];
void add(int u, int v, int w)
{
	edge[cnt].to=v;
	edge[cnt].weight=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}

int dis[100010];
bool vis[100010];
priority_queue<Node>q;
void dijkstra(int s){
	dis[s]=0; vis[s]=true;
	q.push((Node){s,0});
	while(!q.empty())
	{
		int cntnode=q.top().id;
        if(vis[cntnode]) continue;
        q.pop();
        vis[cntnode]=false;
		
		for(int i=head[cntnode]; i!=-1; i=edge[i].next)
		{
			if(dis[edge[i].to]>dis[cntnode]+edge[i].weight)
			{
				dis[edge[i].to]=dis[cntnode]+edge[i].weight;
				if(!vis[edge[i].to])
				{
					vis[edge[i].to]=true;
					q.push((Node){edge[i].to, dis[edge[i].to]});
				}
			}
		}
	}
}

signed main()
{
	memset(head, -1, sizeof(head));
	memset(dis, 0x3f3f3f3f, sizeof(dis));
	
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1,u,v,w;i<=m;i++)
	{
		cin>>u>>v>>w;
		add(u,v,w);
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)
	{
		if(dis[i]==0x3f3f3f3f) cout<<"NA";
		else cout<<dis[i]<<" ";
	}
	return 0;
}

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;