Dijkstra算法优化2：邻接表储存图、优先级队列 (堆) 优化(C语言实现)

谁借莪１个温暖的怀抱￠ 2023-03-01 05:36 83阅读 0赞

在上一节中，我们用邻接表对Dijkstra算法进行优化。在这一小节，我们再加上优先级队列 (堆) 优化，使总的时间复杂度降低到O(N + M) \* logN。值得注意的是，用优先级队列对Dijkstra算法进行优化时，只需要建堆、出列、向上和向下维护堆这4个功能即可。不需要入列。完整的代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    int size = 6; //一共6个点的地图 
    int size2 = 6; //一共6个点的地图 
    int inf = 999; //无穷大
    int distance[6]; //一维数组，记录距离 
    int book[6]; //标记每一个点是否是确定值 
    
    //LinkNode是用于邻接表中，一个结点连接的其它结点 
    //LinkNode只需要有结点的编号、权重即可。 
    struct LinkNode{
        
    	int index = 0;
    	int weight = 0;
    	struct LinkNode * next = NULL; //指向下一个结点 
    };
    
    //声明结构体ArrayNode，用于邻接表中的数组 
    struct ArrayNode{
        
    	struct LinkNode * next = NULL; //指向链表的头结点
    };
    
    //用一个数组存放首元素。每个首元素后面用指针连接各个结点 
    struct ArrayNode arrNode[6]; //这是地图 
    int heap[6]; //优先级队列，这里就叫堆吧。里面的内容是在arrNode中的index 
    int position[6];//记录每个顶点在最小堆中的位置
    
    void showDistance()
    {
        
    	printf("showDistance:\r\n");
    	for(int i = 0; i < size2; i++)
    	{
        
    		printf("%d, ", distance[i]);
    	}
    	printf("\r\n\r\n");
    }
    
    //头插法添加数据，得到的结果的次序是反的
    void addNode(int parentIndex, int nodeIndex, int weight)
    {
        
    	struct ArrayNode * myArrayNode;
    	myArrayNode = &arrNode[parentIndex];
    		
    	//向操作系统申请空间 
    	struct LinkNode *temp = (struct LinkNode *)(malloc(sizeof(struct LinkNode)));
    	temp->index = nodeIndex;
    	temp->weight = weight;
    	temp->next = myArrayNode->next;
    	myArrayNode->next = temp; 
    }
    
    //用map对distance数组进行初始化 
    void initDistance(int startIndex)
    {
        
    	for(int i = 0; i < size; i++) 
    	{
        
    		distance[i] = inf; //初始化，默认距离为infinite 
    	}
    	
    	distance[startIndex] = 0; //起点到自己的距离为0 
    	
    	struct ArrayNode * nodeInArray = &arrNode[startIndex];
    	struct LinkNode *linkNode = nodeInArray->next; //找到与原点直接连接的点 
    	while(linkNode != NULL)	
    	{
        
    		int index = linkNode->index; //与原点直接连接的点的index 
    		distance[index] = linkNode->weight; //初始化的时候，weight就是距离 
    		linkNode = linkNode->next;// 找到下一个结点 
    	}
    }
    
    //Heap数组进行初始化 
    void initHeap()
    {
        
    	for(int i = 0; i < size; i++) 
    	{
        
    		heap[i] = i;
    		position[i] = i;
    	}
    }
    
    //求优先级队列heap中的三个元素的最小值的编号
    //三个参数分别是是father和两个儿子的编号。
    //father一定存在，但两个儿子不一定存在。  
    int getMinIndex(int father, int leftSon, int rightSon)
    {
        
    	int minIndex = father; //默认father是最小值的编号
    	int minDistance = distance[heap[father]]; //最小值 
    	
    	//leftSon < size表示左儿子存在，且左儿子比father更小
    	if(leftSon < size && minDistance > distance[heap[leftSon]])
    	{
        
    		minDistance = distance[heap[leftSon]];//更新最小值
    		minIndex = leftSon; //更新最小值的编号
    	} 
    	if(rightSon < size && minDistance > distance[heap[rightSon]])
    	{
        
    		//minDistance = distance[heap[rightSon]]; //更新最小值
    		minIndex = rightSon; //更新最小值的编号
    	}
    	return minIndex;
    }
    
    //交换优先级队列中的元素。这里要注意，一定要同步更新HeapNode中的indexInHeap 
    void swap(int a, int b) 
    {
        
    	int temp = heap[a];
    	heap[a] = heap[b];
    	heap[b] = temp;
    	
    	//同步更新position中的数据 
    	temp = position[heap[a]];
    	position[heap[a]] = position[heap[b]];
    	position[heap[b]] = temp;
    }
    
    //shiftDown()是部分维护堆，时间复杂度为O(logN)
    //删除元素时用shiftDown(),把数据从上往下调整 
    int shiftDown(int i) //调整以编号为i的元素以下的小顶堆 
    {
        
    	int minIndex = 0; //记录最小值的编号 
    	while(true)
    	{
        
    		//在father和两个儿子之间找到最小值 
    		minIndex = getMinIndex(i, 2 * i + 1, 2 * i + 2);
    		if(minIndex != i) //如果father不是最小值 
    		{
        
    			swap(i, minIndex); //交换最小值和father 
    			i = minIndex; //更新i 
    		}
    		else //如果father是最小值 
    		{
        
    			break; //退出循环 
    		}
    	}
    	return i;
    }
    
    //shiftUp()是部分维护堆，时间复杂度为O(logN)
    //添加元素时用siftUp()，把最底下的元素往上调整 
    int shiftUp(int i)  
    {
        
    	int minIndex = 0; //记录最小值的编号 
    	while(true)
    	{
        	
    		//这个i一定是儿子结点，但不知道是左儿子还是右儿子 
    		//数组从0开始计数，不管i是左儿子还是右儿子，father一定是(i - 1) / 2
    		int father = (i - 1) / 2; 
    		
    		//在father和两个儿子之间找到最小值 
    		minIndex = getMinIndex(father, 2 * father + 1, 2 * father + 2);
    		if(minIndex != father) //如果father不是最小值 
    		{
        
    			swap(father, minIndex); //交换最小值和father 
    			i = father; //更新i，以便下一轮循环重新计算father的值 
    		}
    		else //如果father是最小值 
    		{
        
    			break; //退出循环 
    		}
    	}
    	return i;
    }
    
    //建堆：建堆是最彻底的维护堆。但是时间复杂度较高，为O(N) 
    void createHeap()  
    {
        
    	for(int i = size / 2; i >= 0; i--) //线性建堆 
    	{
        
    		shiftDown(i);
    	}
    } 
    
    //优先级队列出列，得到最小值。
    //出列后要重新维护堆，这样才能保证堆顶元素是最小值 
    int dequeue()  
    {
        
    	if(size <= 0) //防止出错 
    	{
        
    		return -1; //返回-1表示出错 
    	}
    	int minIndex = heap[0]; //记录当前堆中的最小值的编号 
    	
    	//这三行就是堆排序中的一次循环 
    	swap(0, size - 1);//把首元素与尾元素交换
    	size--;//堆的大小-1
    	shiftDown(0);//重新维护堆：向下调整数据
    	 
    	return minIndex; //返回最小值 
    } 
    
    //Dijkstra算法 
    void Dijkstra(int startIndex)
    {
        
    	int count = 0; //确定了最小距离的点的数量
    	book[startIndex] = 1; //起始位置要先标记为已经访问过了 
    	createHeap(); //建堆 
    	dequeue(); // 出列
    	
    	while(count < size2) //这样写代码，形式上与Prim算法高度一致 
    	//遍历每一个点，找最小值。可以用小顶堆优化 
    	//for(int i = 0; i < size2; i++)	
    	{
        
    		int minDistance = distance[heap[0]];//堆顶元素的distance最小 
    		int minIndex = dequeue(); // 出列
    		if(minIndex < 0)
    		{
        
    			break;
    		}
    		
    		printf("minIndex = %d, minDistance = %d\r\n", minIndex, minDistance);
    		book[minIndex] = 1; //估计值变成确定值，标记有最小值的那个点被访问过 
    		count++;
    		
    		//更新distance数组 
    		struct ArrayNode * nodeInArray = &arrNode[minIndex];
    		struct LinkNode * linkNode = nodeInArray->next; //获得与最小距离的结点连接的结点 
    		while(linkNode != NULL)
    		{
        
    			int index = linkNode->index;
    			
    			//更新距离的两个条件：没有被标记过，且距离可以变小 
    			if(book[index] == 0 && distance[index] > linkNode->weight + minDistance)  
    			{
        
    				distance[index] = linkNode->weight + minDistance;
    				
    				//更新一个结点的值，由于更新后的值一定比原先的值小
    				//所以对于小顶堆而言，一定是向上更新 
    				shiftUp(index);
    			}
    			linkNode = linkNode->next; //下一个结点 
    		}
    	}	
    }
    
    //释放资源 
    void releaseResource()
    {
        
    	struct LinkNode * temp; 
    	for(int i = 0; i < size; i++) //把数组中每个点的相邻结点的指针全部释放掉 
    	{
        
    		temp = arrNode[i].next;
    		while(temp != NULL)
    		{
        
    			temp = temp->next; //用temp指向下一个结点。 
    			free(arrNode[i].next); //这时就可以free与arrNode[i]直接连接的结点 
    		}
    	}
    }
    
    //遍历一个结点，和它的所有相连的结点 
    void traverse(int parentIndex)
    {
        
    	struct ArrayNode * myArrayNode = &arrNode[parentIndex];
    	printf("%d --> ", parentIndex); //打印数组中的结点 
    	struct LinkNode * myLinkNode = myArrayNode->next; //链表中的结点 
    	
    	while(myLinkNode != NULL) //链表中的结点不为空 
    	{
        
    		printf("%d (%d) --> ", myLinkNode->index, myLinkNode->weight);
    		myLinkNode = myLinkNode->next;
    	}
    	printf("\r\n");
    }
    
    void traverseAll()
    {
        
    	for(int i = 0; i < size; i++) //对每个节点遍历它的相邻节点
    	{
        
    		traverse(i);
    	}
    }
    
    int main()
    {
        
    	int startIndex = 0; //计算0号点到其它点的最短距离 
    	
    	//插入数据 
    	addNode(0, 1, 10); addNode(0, 2, 16); addNode(0, 3, 14); addNode(1, 0, 10); 
    	addNode(1, 3, 15); addNode(1, 4, 24); addNode(2, 0, 16); addNode(2, 3, 14); 
    	addNode(2, 5, 16); addNode(3, 0, 14); addNode(3, 1, 15); addNode(3, 2, 14);
    	addNode(3, 4, 23); addNode(3, 5, 8);  addNode(4, 1, 24); addNode(4, 3, 23); 
    	addNode(4, 5, 22); addNode(5, 2, 16); addNode(5, 3, 8);  addNode(5, 4, 22);
    	
    	printf("初始状态：\r\n");
    	traverseAll(); //全部遍历 
    	
    	initDistance(startIndex); //初始化distance数组 
    	showDistance(); //显示distance数组 
    	initHeap(); //初始化堆
    	
    	Dijkstra(startIndex);
    	printf("用邻接表、优先级队列优化之后，Dijkstra算法的结果：\r\n");
    	showDistance(); //显示distance数组 
    	
    	releaseResource(); //释放内存 
    	printf("Hello\r\n"); //释放内存之后，再访问就会出错。具体表现为无法打印Hello
    	return 0;
    }

计算结果如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]上述就是用邻接表、优先级队列 (堆) 优化的Dijkstra算法。优化之后的时间复杂度为(N + M) \* logN。这个算法适用于稀疏图，如果用在稠密图中，速度还不如优化前的Dijkstra算法。所以要搞清楚被研究的图是什么性质的再选择算法。另外，优化后的Dijkstra算法同样不适用于带有负权回路的图。这个算法用C语言实现比较复杂，如果用C++实现就会简单很多，原因是C++中已经实现了链表、优先级队列等算法，只需要直接调用这些算法就可以了。关于这部分内容就请小伙伴们自己上网搜索吧。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/9b878d8ec5724f11a11005315ae1a819.png