欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

贪心算法:单源最短路径 Dijkstra算法

程序员文章站 2024-03-17 09:01:22
...

Dijkstra算法的思想与Prim算法类似而又不同,都是一步一步将点纳为一个集合,但Dijkstra下一步是寻找离源点最近的点将其纳入。

每个点上会记录两个信息:上一个点是哪个以及离源点的距离。每次我们纳入新点之后,要实时更新离源点的信息。

我们使用pre数组来回溯上一个点是哪个,再用length数组记录距离。
贪心算法:单源最短路径 Dijkstra算法
如图,以0为源点,判断到8的最短距离。

最开始的集合为
0 1 2 3 4 5 6 7 8
0 1 5 X X X X X X
易得离1最近,我们选取1.

更新距离时,由“由1搭桥更近还是自己现在的值更近”和“该点是否已经在集合里”来判断是否替换。
如果“搭桥更近”pre数组会记录下这个桥。

更新之后为
0 1 2 3 4 5 6 7 8
0 1 4 8 6 X X X X
易得2最近。将2填入。再次更新。
0 1 2 3 4 5 6 7 8
0 1 4 8 5 11 X X X
再得4最近,继续更新。
0 1 2 3 4 5 6 7 8
0 1 4 7 5 11 11 X X
以此类推。

上面还有代码是我萌新的时候写的,所以有些不成熟的地方。

void dijkstra(int g[9][9]){	
	int length[9];	
	for (int i = 0;i < 9;i++)		
		length[i] = g[0][i]; 	
	int pre[9];	
	pre[0] = -1; 	
	int included[9] = { 1,0,0,0,0,0,0,0,0 };	
	for (int roads = 8;roads > 0;roads--)	
	{		
		int min = X;		
		int minid;		
		for (int i = 0;i < 9;i++)		
		{			
			if (min > length[i]&&!included[i]){
				min = length[i];
                                minid=i;			
                        }		
                }		
                included[minid] = 1;		
                for (int i = 0;i < 9;i++){			
                	if (!included[i] && length[i] > min + g[minid][i]){				
                		length[i] = min + g[minid][i];				 
                		pre[i]=minid;			
                	}	
                }	
        } 	
        for (int i = 1;i < 9;i++){		
        	printf("0->%d %d\n", i, length[i]);	
        }	
        int i = 8;	
        while (i >= 0){		
        	printf("%d ", i);		
        	i = pre[i];	
        }	
        printf("0\n");
}

转载注明出处。