蓝桥杯之最短路径算法

Dijkstra算法

算法思想

该算法是典型的单元最短路径算法，用于计算一个节点到其他所有节点的最短路径

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止

实际上是为了计算从起始节点到其他所有节点的最短路径

代码实现

using uint = unsigned int;
const uint INF = 2160000;
//int Dijkstra(vector<vector<uint>>& graph, int start, int end)
//{
//	//表示起始节点到每个节点的距离
//	vector<uint>dis(graph.size(), 0);
//	//表示节点在s集合中（true），在u集合中为（false）
//	vector<bool>use(graph.size(), 0);
//	vector<int>path(graph.size(), 0);
//	//初始化dis
//	for (int i = 0; i < graph.size(); i++)
//	{
//		dis[i] = graph[start][i];
//	}
//	//将起始节点放到s集合中
//	use[start] = true;
//	path[start] = 1;
//	//开始将u集合中的节点依次放到s集合中
//	for (int j = 1; j < graph.size(); j++)
//	{
//		//找权值最小的节点
//		int k = -1;//记录该节点的下标
//		int min = 0xff;//记录该节点的权值
//		for (int i = 0; i < graph.size(); i++)
//		{
//			if (use[i] == false && dis[i] < min)
//			{
//				min = dis[i];
//				k = i;
//			}
//		}
//		if (k == -1)
//		{
//			break;
//		}
//		//将该节点放到s集合里,还要更新u集合里的权值
//		use[k] = true;
//		for (int i = 0; i < graph.size(); i++)
//		{
//			if (use[i] == false && min + graph[k][i] < dis[i])
//			{
//				dis[i] = min + graph[k][i];
//				path[k] = 1;
//			}
//		}
//	}
//	for (int i : path)
//	{
//		cout << i << " ";
//	}
//	cout << endl;
//	return dis[end];
//}
//优先级队列的优化
int Dijkstra(vector<vector<uint>>& graph, int start, int end)
{
	//表示起始节点到每个节点的距离
	vector<uint>dis(graph.size(), 0);
	//表示节点在s集合中（true），在u集合中为（false）
	vector<bool>use(graph.size(), 0);
	vector<int>path(graph.size(), 0);
	//用优先级队列（设置为小根堆），在找权值最小的节点中可以节约时间
	priority_queue<pair<uint , int>, vector<pair<uint, int>>, greater<pair<uint, int>>>que;
	//将起始节点放到s集合中
	use[start] = true;
	path[start] = 1;
	//初始化dis
	for (int i = 0; i < graph.size(); i++)
	{
		dis[i] = graph[start][i];
		//将除起始外的元素全部放在队列里面
		if(i!=start)
			que.emplace(dis[i],i);
	}
	while(!que.empty())
	//开始将u集合中的节点依次放到s集合中	while(!que.empty())
	{
		//因为我用的是优先级队列，那么队列首的元素一定是权值最小的元素
		auto pair = que.top();
		que.pop();
		//找权值最小的节点
		int k = pair.second;//记录该节点的下标
		uint min = pair.first;//记录该节点的权值
		if (min == INF)
		{
			break;
		}
		if (use[k])
			continue;
		//将该节点放到s集合里,还要更新u集合里的权值
		use[k] = true;
		for (int i = 0; i < graph.size(); i++)
		{
			if (use[i] == false && min + graph[k][i] < dis[i])
			{
				dis[i] = min + graph[k][i];
				path[k] = 1;
				//更新队列里的值
				que.emplace(dis[i], i);
			}
		}
	}
	for (int i : path)
	{
		cout << i << " ";
	}
	cout << endl;
	return dis[end];
}
int main()
{
	vector<vector<uint>>graph = {
		{0,6,3,INF,INF,INF},
		{6,0,2,5,INF,INF},
		{3,2,0,3,4,INF},
		{INF,5,3,0,2,3},
		{INF,INF,4,2,0,5},
		{INF,INF,INF,3,5,0}
	};
	//int distance = Dijkstra(graph, 1, 3);
	//cout << distance;
	 

Floyd算法

算法思想

多源最短路径算法：又称插点法，是一种利用动态规划思想寻找给定的加权图中多元点之间的算法主要思想是：

1，从第1个点到第n个点依次加入图中，每个点加入后进行试探是否有最短路径长度被更改，具体方法是遍历图中每一个节点（i，j双重循环），判断每一个点对距离是否因为加入的点而发生最小的距离变化，如果发生，就更新两点（i，j）的距离

2，重复上述直到最后插点完成

代码实现

	vector<vector<uint>>graph = {
		{0,6,3,INF,INF,INF},
		{6,0,2,5,INF,INF},
		{3,2,0,3,4,INF},
		{INF,5,3,0,2,3},
		{INF,INF,4,2,0,5},
		{INF,INF,INF,3,5,0}
	};
	//int distance = Dijkstra(graph, 1, 3);
	//cout << distance;
	 
	 
	 
	
	//floyd算法
	for (int k = 0; k < graph.size(); k++)
	{
		for (int i = 0; i < graph.size(); i++)
		{
			for (int j = 0; j < graph.size(); j++)
			{
				graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
			}
		}
	}
	for (auto i : graph)
	{
		for (auto j : i)
		{
			cout << j << " ";
		}
		cout << endl;
	}
	return 0;