图的最短路径问题（C++）

图的最短路径问题（C++）

        最短路径问题主要分为两种，单源和多源。

        对于无权的单源最短路径问题，因其所有边长相等，在使用广度优先搜索时距离一定是从0开始依次向外扩展一层，不会突然出现一个顶点使得之前录入的路径缩短。

        那么就只需要在广度优先搜索的过程中加入可以记录距离和路径的容器即可。

class unweighted
{
public:
	vector>map;//邻接矩阵
	vectordis;//记录距离的容器
	vectorpath;//记录路径的容器

	void creat()
	{
		cout << "请输入元素个数：" << endl;
		int num;
		cin >> num;
		map.resize(num);
		dis.resize(num);
		path.resize(num);

		for (int i = 0; i < num; i++)
		{
			map[i].resize(num);
		}

		for (int i = 0; i < num; i++)
		{
			for (int j = 0; j < num; j++)
			{
				if (i == j)
					map[i][j] = 0;
				else
					map[i][j] = -1;
			}
		}

		cout << "请输入数据个数：" << endl;
		int row;
		cin >> row;

		int number = 0;
		while (number < row)
		{
			int begin;
			int end;
			cin >> begin >> end;
			map[begin - 1][end - 1] = 1;//数据存储以下标0为起点，而我们的输入以1为起点
			number++;
		}

	}

	void Unweighted()
	{
		cout << "请输入源点：" << endl;
		int v;
		cin >> v;
		v--;
		dis.assign(dis.size(),-1);//距离容器中除了源点本身，其他顶点初始化为-1
		dis[v] = 0;
		path.assign(path.size(), -1);//路径全部初始化为-1
		queueq;//用队列进行广度优先搜索
		q.push(v);
		while (!q.empty())
		{
			int w = q.front();//删掉队列头部顶点并把该顶点的未被访问过的邻接点放入队列
			q.pop();
			for (unsigned int i = 0; i < map.size(); i++)
			{
				if (map[w][i] == 1 && dis[i] == -1)//dis[i]为-1说明未被访问
				{
					dis[i] = dis[w] + 1;
					path[i] = w + 1;
					q.push(i);
				}
			}
		}
	}
};

对于有权的单源最短路径，使用Dijkstra算法，为了保证每次录入的顶点一定是最短路径经过的顶点，我们需要引入贪心算法，即每次从可访问的顶点中挑一个距离最小的，当然此时距离容器中非邻接点将被初始化为正无穷以保证距离最小的顶点可以成功被挑选出来，这时这个距离最小的顶点也一定是已访问顶点的邻接点。

 

class dijkstra
{
public:
	vector>map;
	vectordis;
	vectorpath;

	void creat()
	{
		cout << "请输入元素个数" << endl;
		int num;
		cin >> num;
		map.resize(num);
		dis.resize(num);
		path.resize(num);
		for (int i = 0; i < num; i++)
		{
			map[i].resize(num);
			dis[i] = INF;
		}

		for (int i = 0; i < num; i++)
		{
			for (int j = 0; j < num; j++)
			{
				if (i == j)
					map[i][j] = 0;
				else
					map[i][j] = INF;//这时需要将距离初始化为正无穷
			}
		}
		cout << "请输入数据数量：" << endl;
		int row;
		cin >> row;
		int number = 0;
		while (number < row)
		{
			int begin;
			int end;
			int side;
			cin >> begin >> end >> side;
			map[begin - 1][end - 1] = side;
			number++;
		}

	}

	void Dijkstra()
	{
		cout << "请输入源点" << endl;
		int v;
		cin >> v;
		v--;
		for (unsigned int i = 0; i < map.size(); i++)
		{
			dis[i] = map[v][i];
			if (map[v][i] == INF || i==0)//将源点的非邻接点路径初始化为-1
				path[i] = -1;
			else
				path[i] = v + 1;//将源点的邻接点路径初始化为源点
		}
		vectorcollected;//用这个容器记录已访问的顶点
		collected.assign(map.size(), false);
		collected[0] = true;

		while (1)
		{
			int V = 0;//用V记录dis中最小元素的下标
			bool check = true;//用这个判断collected中元素是否都已被访问过
			int min = INF;//用这个记录当前最小元素
			for (unsigned int i = 0; i < map.size(); i++)
			{
				if (collected[i] == true)
					continue;
				if (min > dis[i])
				{
					min = dis[i];
					V = i;
					check = false;
				}
			}
			if (check == true)
				break;
			collected[V] = true;//将挑选的元素标记为已访问

			for (unsigned int i = 0; i < map.size(); i++)
			{
				if (collected[i] == false)//对所有未被访问的V的邻接点计算距离
				{它们之间的
					if(dis[V] + map[V][i] < dis[i])//如果V的邻接点的距离比V的距离加边的长度要长，更新邻接点的距离，并更新路径
					{
						dis[i] = dis[V] + map[V][i];
						path[i] = V + 1;
					}
				}
			}
		}
	}
};

对于有权的多源最短路径，当然可以对每个顶点做一遍Dijkstra算法，但有更聪明的Floyd算法，对于一条路径来说，如果有一个路径外的顶点，使得经过该点的路径的距离比之前的要短，那么新的路径就是更短的路径，如此反复就会得到最短的路径。

class floyd
{
public:
	vector>map;
	vector>dis;

	void creat()
	{
		cout << "请输入元素个数：" << endl;
		int num;
		cin >> num;
		map.resize(num);
		dis.resize(num);
		for (int i = 0; i < num; i++)
		{
			map[i].resize(num);
			dis[i].resize(num);
		}

		for (int i = 0; i < num; i++)
		{
			for (int j = 0; j < num; j++)
			{
				if (i == j)
					map[i][j] = 0;
				else
					map[i][j] = INF;
				dis[i][j] = -1;
			}
		}

		cout << "请输入要输入的数据数量：" << endl;
		int row;
		cin >> row;
		int number = 0;

		while (number < row)
		{
			int begin;
			int end;
			int side;
			cin >> begin >> end >> side;
			map[begin - 1][end - 1] = side;
			dis[begin - 1][end - 1] = begin;
			number++;
		}
	}

	void Floyd()
	{
		for (unsigned int k = 0; k < map.size(); k++)//对每个顶点做一遍算法
		{
			for (unsigned int i = 0; i < map.size(); i++)//起点
			{
				for (unsigned int j = 0; j < map.size(); j++)//终点
				{
					if (map[i][j] > map[i][k] + map[k][j])
					{
						map[i][j] = map[i][k] + map[k][j];
						dis[i][j] = k + 1;
					}
				}
			}
		}
	}
};