贪心算法：Dijkstra算法

痛定思痛。 2022-05-09 14:22 200阅读 0赞

求顶点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

![70][]

![70 1][]

![70 2][]

思路：将所有的顶点分为两部分，已知最短路径的顶点集合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<无穷大，该更新

![70 3][]

然后又开始新一轮的比较，重复步骤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; 
    	 
    }

[70]: /images/20220506/e350ddfc653e4bd6af166d45d79988aa.png
[70 1]: /images/20220506/61450cfe0b124b1db8408f126a0a8eb3.png
[70 2]: /images/20220506/3ee6db66a4b349ed863f2619913a738f.png
[70 3]: /images/20220506/92a55a5ccc7f4224b6f54c7b99bd769e.png