放牧代码和思想
专注自然语言处理、机器学习算法
    愛しさ 優しさ すべて投げ出してもいい

图的最短路算法初步

码农场 > 编程开发 > 算法 2014-03-30 阅读(5864) 评论(1)

目录

对图的几种初级算法做个总结，温故知新。

最短路问题

Bellman-Ford和Dijkstra的递推公式都是d[i] = min{d[j] + cost[i to j]}。

单源最短路之Bellman-Ford算法

适用于无原点s可达负圈的任意图，复杂度O(|V|*|E|)。

如果负圈存在的话，会陷入死循环。但是可以利用这一性质来判断是否有负圈：

#include <iostream>
using namespace std;

#define MAX_E 1024

// 从顶点from指向顶点to的权值为cost的边
struct edge
{
	int from, to, cost;
	edge(){}
	edge(int from, int to, int cost)
	{
		this->from = from;
		this->to = to;
		this->cost = cost;
	}
};

// 边
edge es[MAX_E];

// 最短距离
int d[MAX_E];
// V是顶点数，E是边数
int V, E;

// 求解从顶点s出发到所有点的最短距离
void shortest_path(int s)
{
	memset(d, 0x3f, V * sizeof(int));
	d[s] = 0;
	while (true)
	{
		bool update = false;
		for (int i = 0; i < E; ++i)
		{
			edge e = es[i];
			if (d[e.from] != 0x3f3f3f3f && d[e.to] > d[e.from] + e.cost)
			{
				d[e.to] = d[e.from] + e.cost;
				update = true;
			}
		}
		if (!update)
		{
			break;
		}
	}
}

// 是否存在负圈
bool find_negative_loop()
{
	memset(d, 0, sizeof(d));
	for (int i = 0; i < V; ++i)
	{
		for (int j = 0; j < E; ++j)
		{
			edge e = es[j];
			if (d[e.to] > d[e.from] + e.cost)
			{
				d[e.to] = d[e.from] + e.cost;
				// 如果更新了V次，则存在负圈
				if (i == V - 1)
				{
					return true;
				}
			}
		}
	}
	return false;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	// 测试数据
	V = 7;
	E = 20;
	es[0] = edge(0, 1, 2);
	es[1] = edge(0, 2, 5);
	es[2] = edge(1, 2, 4);
	es[3] = edge(1, 3, 6);
	es[4] = edge(1, 4, 10);
	es[5] = edge(2, 3, 2);
	es[6] = edge(3, 5, 1);
	es[7] = edge(4, 5, 3);
	es[8] = edge(4, 6, 5);
	es[9] = edge(5, 6, 9);
	// 无向图必须重复一遍
	es[10] = edge(1, 0, 2);
	es[11] = edge(2, 0, 5);
	es[12] = edge(2, 1, 4);
	es[13] = edge(3, 1, 6);
	es[14] = edge(4, 1, 10);
	es[15] = edge(3, 2, 2);
	es[16] = edge(5, 3, 1);
	es[17] = edge(5, 4, 3);
	es[18] = edge(6, 4, 5);
	es[19] = edge(6, 5, 9);
	// 测试数据结束
	cout << "negative loop ? " << boolalpha << find_negative_loop() << endl;
	shortest_path(0);
	cout << d[V - 1] << endl;
	system("pause");
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

单源最短路之Dijkstra算法

Bellman-Ford机械地遍历每一条边，浪费时间。Dijkstra算法每次循环都从最短距离已经确定的顶点出发，如果用堆储存最短距离的状态的话，复杂度降低为O(|E|log|V|)。这里的“最短距离已经确定”的前提是，没有负权重使得此最短距离变小，所以Dijkstra不能用于负边。举个例子说明Dijkstra为什么不能有负边：

1->2  2 

1->3 100 

3->2 -99 

求从1开始的单源最短路的话会得到1->2最短路是2的错误结果。这是还是需要使用Bellman-Ford算法。

一份实现：

#include <iostream>
#include <queue>
#include <functional>
using namespace std;

#define MAX_V 1024

// 从顶点from指向顶点to的权值为cost的边
struct edge
{
	int to, cost;
	edge(){}
	edge(int to, int cost)
	{
		this->to = to;
		this->cost = cost;
	}
};

// first 最短路径，second顶点编号
typedef pair<int, int> P;

// 边
vector<edge> G[MAX_V];

// 最短距离
int d[MAX_V];
// V是顶点数，E是边数
int V, E;

// 求解从顶点s出发到所有点的最短距离
void dijkstra(int s)
{
	priority_queue<P, vector<P>, greater<P> > que;
	memset(d, 0x3f, V * sizeof(int));
	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));
			}
		}
	}
}


///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	// 测试数据
	V = 7;
	E = 20;
	G[0].push_back(edge(1, 2));
	G[1].push_back(edge(0, 2));
	G[0].push_back(edge(2, 5));
	G[2].push_back(edge(0, 5));
	G[1].push_back(edge(2, 4));
	G[2].push_back(edge(1, 4));
	G[1].push_back(edge(3, 6));
	G[3].push_back(edge(1, 6));
	G[1].push_back(edge(4, 10));
	G[4].push_back(edge(1, 10));
	G[2].push_back(edge(3, 2));
	G[3].push_back(edge(2, 2));
	G[3].push_back(edge(5, 1));
	G[5].push_back(edge(3, 1));
	G[4].push_back(edge(5, 3));
	G[5].push_back(edge(4, 3));
	G[4].push_back(edge(6, 5));
	G[6].push_back(edge(4, 5));
	G[5].push_back(edge(6, 9));
	G[6].push_back(edge(5, 9));
	// 测试数据结束
	dijkstra(0);
	cout << d[V - 1] << endl;
	system("pause");
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

路径还原

如果要求解最短路径途经的各点，只需定义一个prev[j]来记录最短路径上顶点j的前驱即可。

#include <iostream>
#include <queue>
#include <functional>
#include <vector>
#include <iterator>
using namespace std;

#define MAX_V 1024

// 从顶点from指向顶点to的权值为cost的边
struct edge
{
	int to, cost;
	edge(){}
	edge(int to, int cost)
	{
		this->to = to;
		this->cost = cost;
	}
};

// first 最短路径，second顶点编号
typedef pair<int, int> P;

// 边
vector<edge> G[MAX_V];

// 最短距离
int d[MAX_V];
// V是顶点数，E是边数
int V, E;

int prev_vertex[MAX_V];	// 最短路上的前驱顶点

// 求解从顶点s出发到所有点的最短距离
void dijkstra(int s)
{
	priority_queue<P, vector<P>, greater<P> > que;
	memset(d, 0x3f, V * sizeof(int));
	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));
				prev_vertex[e.to] = v;
			}
		}
	}
}

// 到顶点t的最短路
vector<int> get_path(int t)
{
	vector<int> path;
	for (; t != -1; t = prev_vertex[t])
	{
		path.push_back(t);
	}
	reverse(path.begin(), path.end());
	return path;
}


///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	prev_vertex[0] = -1;
	// 测试数据
	V = 7;
	E = 20;
	G[0].push_back(edge(1, 2));
	G[1].push_back(edge(0, 2));
	G[0].push_back(edge(2, 5));
	G[2].push_back(edge(0, 5));
	G[1].push_back(edge(2, 4));
	G[2].push_back(edge(1, 4));
	G[1].push_back(edge(3, 6));
	G[3].push_back(edge(1, 6));
	G[1].push_back(edge(4, 10));
	G[4].push_back(edge(1, 10));
	G[2].push_back(edge(3, 2));
	G[3].push_back(edge(2, 2));
	G[3].push_back(edge(5, 1));
	G[5].push_back(edge(3, 1));
	G[4].push_back(edge(5, 3));
	G[5].push_back(edge(4, 3));
	G[4].push_back(edge(6, 5));
	G[6].push_back(edge(4, 5));
	G[5].push_back(edge(6, 9));
	G[6].push_back(edge(5, 9));
	// 测试数据结束
	dijkstra(0);
	cout << d[V - 1] << endl;
	auto path = get_path(V - 1);
	copy(path.begin(), path.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	system("pause");
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

输出：

16
0 2 3 5 4 6
请按任意键继续. . .

任意两点之间的距离Floyd-Warshall算法

d[u][v]表示边e=(u,v)的权值，不存在的时候等于无穷大或者d[i][i] = 0

在只是用顶点0~k和i,j的情况下，记i到j的最短路径长度为d[k+1][i][j]，如果这次不经过顶点k那么d[k][i][j] = d[k-1][i][j]，否则d[k][i][j] = d[k-1][i][k] + d[k-1][k][j]，两种情况取小值作为d的值。注意到第一个下标k是冗余的，于是忽略它。

Floyd-Warshall算法三重循环，实现起来非常简单。复杂度于是成为O(|V|3)；可以处理负边，如果需要判断图中是否存在负圈，只需检查d中是否有负数即可。

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_V 1024
int d[MAX_V][MAX_V];	//	d[u][v]表示边e=(u,v)的权值，不存在的时候等于无穷大或者d[i][i] = 0
int V;					//	顶点数

void warshall_floyd()
{
	for (int k = 0; k < V; ++k)
	{
		for (int i = 0; i < V; ++i)
		{
			for (int j = 0; j < V; ++j)
			{
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	// 测试数据
	V = 7;
	memset(d, 0x3f, V * MAX_V * sizeof(int));
	d[0][1] = 2;
	d[0][2] = 5;
	d[1][2] = 4;
	d[1][3] = 6;
	d[1][4] = 10;
	d[2][3] = 2;
	d[3][5] = 1;
	d[4][5] = 3;
	d[4][6] = 5;
	d[5][6] = 9;
	// 无向图必须重复一遍
	d[1][0] = 2;
	d[2][0] = 5;
	d[2][1] = 4;
	d[3][1] = 6;
	d[4][1] = 10;
	d[3][2] = 2;
	d[5][3] = 1;
	d[5][4] = 3;
	d[6][4] = 5;
	d[6][5] = 9;
	warshall_floyd();
	cout << d[0][V - 1] << endl;
	system("pause");
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享：码农场 » 图的最短路算法初步

继续浏览有关 算法 的文章

评论 1

取消

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的作品

HanLP自然语言处理包《自然语言处理入门》