图算法——《挑战程序设计竞赛》

发表于 | 分类于 | 浏览次数
字数统计: 864 字 | 阅读时长 ≈ 4 分钟

2.5.2 图的表示

邻接表可以直接用如下代码表示：

1
2
3
4
5
6
vector<int> graph[MAX_V] 来表示邻接表 
/*
边上有属性的情况：
	struct edge {int to, cost;}
	vector<edge> G[MAX_V];
*/

2.5.4 最短路问题

1. 单源最短路问题

Bellman-Ford算法
记从起点s出发到顶点i的最短距离为d[i]，则下述等式成立：

设初值d[s]=0, d[i]=INF，再不断使用这条递推关系式更新d的值。只要图中不存在负圈，这样的更新操作就是有限的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct edge {int from, to, cost};
edge es[MAX_E]; //边
int d[MAX_V];
int V, E;
void shortest_path(int s)
{
	for(int i=0;i<V;i++) d[i] = INF;
	d[s] = 0;
	while(true)
	{
		bool update = false;
		for(int i=0;i<E;i++)
		{
			edge e = es[i];
			if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost)
			{
				d[e.to] = d[e.from] + e.cost;
				update = true;
			}
		}
		if(!update) break;
	}
	
}

如果图中不存在负圈，最短路径不会经过同一个顶点两次，while(true)最多执行|V|-1次（|V|个顶点，|V|-1条边），因此复杂度为 $O(|V|\times|E|)$。反之如果存在负圈，那么第|V|次循环种也会更新d的值，因此可以通过判断第V次是否仍更新了判断是否存在负圈。

Dijkstra算法
在没有负边的情况下，上述Bellman-Ford算法复杂度高很大一部分原因是，如果d[i]还不是最短距离即使进行d[j]=d[i]+(从i到j的边的权值)的更新，d[j]也不会是最短距离，而且即使d[i]没有变化，每一次循坏也要检查一遍从i出发的所有边，很浪费时间。因此可以对算法做出如下修改：

  • 找到最短距离已经确定的顶点，从它出发更新相邻顶点的最短距离
  • 此后不用再关心1中的“最短距离已经确定的顶点”

下面是使用STL的priority_queue的实现。在每次更新时往堆里插入当前最短距离和顶点的值对，当取出的最小值不是最短距离时，就丢弃这个值。

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
struct edge{int to, cost;};
typedef pair<int, int> P;
int V;
vector<edge> G[MAX_V];
int d[MAX_V];
void dijkstra(int s)
{
	priority_queue<P, vector<P>, greater<P> > que;
	fill(d,d+V,INF);
	d[s] = 0;
	que.push(P(0,s));
	while(!que.empty())
	{
		P p = que.top(); que.pop();
		int v = p.second;
		if(d[v] < p.first) continue;
		for(int i=0;i<G[v].size();i++)
		{
			edge e = G[v][i];
			if(d[e.to] > d[v]+e.cost)
			{
				d[e.to] = d[v]+e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
}

2.5.6 图算法的应用

一共有n头牛，按编号顺序排成一排，有ml个关系好的牛的信息，有md个关系不好的牛的信息，对应输入的第一行的三个元素，接下来ml行，每行三个元素A,B,D，表示A牛和B牛相距不希望超过D，接下来md行，每行三个元素A,B,D表示A牛和B牛的相距至少要有D才行。求1号牛和n号牛的最大距离，如果距离无限大输出-2，如果无解输出-1。

记第i头牛的位置是d[i]。首先，牛是按照编号顺序排列的，所以有$d[i] \le d[i+1]$。