yuzh的博客

❤ ECUST ❤

0%

单源最短路径

发表于 更新于 Valine：

模板：洛谷P3371 单源最短路径（弱化版）

Bell-man Ford算法

在每一轮对每个点进行松弛，即比较目标点当前的最短路径和出发点最短路径与边权相加的值，取最小值作为最短路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int edg[100010][3];
int D[100010];

void bellman(int v)
{
	memset(D,0x3f,sizeof(D));
	D[v]=0;
	for(int i=1;i<n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(D[edg[j][1]]>D[edg[j][0]]+edg[j][2])
				D[edg[j][1]]=D[edg[j][0]]+edg[j][2];
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<D[i]<<" ";
	}
}

SPFA算法

设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点hd，并且用hd点当前的最短路径估计值对离开hd点所指向的结点to_node进行松弛操作，如果to_node点的最短路径估计值有所调整，且to_node点不在当前的队列中，就将to_node点放入队尾。

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
void spfa(int root)
{
	memset(D,0x7f7f7f7f,sizeof(D));
	D[root]=0;
	queue<int>Q;
	Q.push(root);
	inq[root]=1;
	
	//当队列不为空
	while(!Q.empty())
	{
		int hd=Q.front();//取出队首节点
		for(int i=0;i<M[hd].size();i++)
		{
			edg e=M[hd][i];
			if(D[e.to_node]>D[hd]+e.value)
			{
				D[e.to_node]=D[hd]+e.value;
				if(inq[e.to_node]==0)
				{
					inq[e.to_node]=true;
					Q.push(e.to_node);
				}
			}
		}
		inq[hd]=0;
		Q.pop();
	}
	
	for(int i=1;i<=n;i++)
	{
		cout<<D[i]<<" ";
	}
}

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
vector<edg>M[maxn];
int D[maxn],used[maxn];

void djs(int root)
{
	memset(D,0x7f7f7f7f,sizeof(D));
	D[root]=0;
	
	for(int i=1;i<n;i++)
	{
		int mx=1;
		while(used[mx]==true && mx<=n) mx++;//找到未被使用的点
		for(int j=1;j<=n;j++)
		{
			if(used[j]==false && D[mx]>D[j])
			{
				mx=j;//定位到第一个没有被确认的点 
				break;
			}
		}
		used[mx]=true;
		for(int j=0;j<M[mx].size();j++)
		{
			edg e=M[mx][j];
			if(D[e.to_node]>D[mx]+e.value)
			{
				D[e.to_node]=D[mx]+e.value;
			}
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		cout<<D[i]<<" ";
	}
}