贪心算法：Dijkstra算法

求顶点1到各个顶点的最短路径。

输入：

6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4

输出：

0 1 8 4 13 17

贪心算法：Dijkstra算法

思路：将所有的顶点分为两部分，已知最短路径的顶点集合p和未知最短路径的集合Q，最开始，p中只有一个顶点1，可以用book数组记录哪些顶点在p中。

1.对边，dis数组、book数组初始化

int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min;
	int inf=99999999;
	cin >> n >> m;//n表示点，m表示边
	//初始化
 	for(i = 1; i <= n; ++i)
 	{
 		for(j = 1; j <= n; ++j)
 		{
 			if(i==j) e[i][j] = 0;
 			else e[i][j] = inf;
		 }
	 }
	//读入数据
	while(m--)
	{
		cin >> t1 >> t2 >> t3;
		e[t1][t2] = t3;
	} 
	
	//初始化dis数组，这里为1号顶点到其余各个顶点的距离
	for(i = 1; i <= n; ++i)
	{
		dis[i] = e[1][i];
	} 
	
	//book数组初始化
	for(i = 1; i <= n; ++i)
		book[i] = 0;
	book[1] = 1;//刚开始1加入最短路径的数组

2.先在dis中选择一个最短路径，其顶点假设为u，将其加入到顶点p中，book[u]=1;

	min = inf;
		for(j = 1; j <= n; ++j)//找到dis[]中的最小值，并将最小值所在的点加入到集合中 
		{
			if(book[j] == 0 && dis[j] < min)
			{
				min = dis[j];
				u = j;
			}
		}
		book[u] = 1;

3. 然后更新最小值。先选择与u相邻的顶点，看看dis[u]+e[u][v]的和和原来的dis[v]那个大，如果dis[u]+e[u][v]<dis[v]，就更新最小值,知道与u相邻的顶点最小值都更新完为止。

for(v = 1; v <= n; ++v)
		{
			if(e[u][v]<inf) //u和v两个点右边相连
			{
				if(dis[u]+e[u][v] < dis[v])//更新最小值 
					dis[v] = dis[u]+e[u][v];
			} 
		}

举例：

比如经过第2步，我们集合p中应该加入2，因为2的路径最短。

再看与2相邻的顶点有3和4，然后我们看看有没有必要更新3、4的值。

3： dis[2]+e[2][3]=1+4 = 5 <12,所以dis[3]=5，该更新；

4：dis[2]+e[2][4]=1+3=4<无穷大，该更新

贪心算法：Dijkstra算法

然后又开始新一轮的比较，重复步骤2和步骤3。for(i=1; i < n; ++i)一共要比较n-1次。

#include<iostream>
using namespace std;
int main()
{
	freopen("a.txt","r",stdin);
	int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min;
	int inf=99999999;
	cin >> n >> m;//n表示点，m表示边
	//初始化
 	for(i = 1; i <= n; ++i)
 	{
 		for(j = 1; j <= n; ++j)
 		{
 			if(i==j) e[i][j] = 0;
 			else e[i][j] = inf;
		 }
	 }
	//读入数据
	while(m--)
	{
		cin >> t1 >> t2 >> t3;
		e[t1][t2] = t3;
	} 
	
	//初始化dis数组，这里为1号顶点到其余各个顶点的距离
	for(i = 1; i <= n; ++i)
	{
		dis[i] = e[1][i];
	} 
	
	//book数组初始化
	for(i = 1; i <= n; ++i)
		book[i] = 0;
	book[1] = 1;//刚开始1加入最短路径的数组
	
	for(i = 1; i <= n-1; ++i)
	{
		min = inf;
		for(j = 1; j <= n; ++j)//找到dis[]中的最小值，并将最小值所在的点加入到集合中 
		{
			if(book[j] == 0 && dis[j] < min)
			{
				min = dis[j];
				u = j;
			}
		}
		book[u] = 1;
		//再以u为起点对每一条边进行松弛操作
		for(v = 1; v <= n; ++v)
		{
			if(e[u][v]<inf) //u和v两个点右边相连
			{
				if(dis[u]+e[u][v] < dis[v])//更新最小值 
					dis[v] = dis[u]+e[u][v];
			} 
		} 
	} 
	
	//输出结果
	for(i = 1; i <= n; ++i)
		cout << dis[i] << " ";
	cout << endl;
	return 0; 
	 
}

贪心算法：Dijkstra算法

相关推荐