Dijkstra算法的优化1:用邻接表储存图(C语言实现)

矫情吗；* 2023-03-01 05:35 126阅读 0赞

Dijkstra算法的优化主要体现在两个方面：  
1、使用邻接表代替邻接矩阵，这样每次更新distance数组时，读取到的点都是与minIndex直接连接的点，而不用读取不直接连接的点。这样做的效率显然比较高。  
2、用优先级队列代替遍历方式寻找距离源点最近的点。时间复杂度从O(N) 降低为O(logN)。

为了让读者更加容易接受，我们将分段实现优化。我们先用邻接表对Dijkstra算法进行优化。之后再加上优先级队列 (堆) 优化。为了简单起见，Dijkstra算法的优化代码不输出具体路径。

## 用邻接表储存图的Dijkstra算法： ##

用邻接表代替邻接矩阵，其实就是把图的储存方式换了一下。当然，这样操作之后，Dijkstra算法中读取边长的代码也就会有相应的改动，但是这些改动是很小的。

#include <stdio.h>
    #include <stdlib.h>
    
    int size = 6; //一共6个点的地图 
    int inf = 999; //无穷大
    int distance[6]; //一维数组，记录距离 
    int book[6]; //标记每一个点是否是确定值 
    
    //声明链表结点的结构体 
    struct LinkNode{
        
    	int index = 0;
    	int weight = 0;
    	struct LinkNode * next = NULL;
    };
    
    //声明数组元素的结构体
    struct ArrayNode{
        
    	struct LinkNode * next = NULL; //指向链表
    };
    
    //用一个数组存放首元素。每个首元素后面用指针连接各个结点 
    struct ArrayNode arrNode[6]; //这是地图 
    
    //头插法。得到的结果的次序是反的 
    void addNode(int parentIndex, int nodeIndex, int weight)
    {
        
    	struct ArrayNode * currentNode;
    	currentNode = &arrNode[parentIndex];
    	
    	//向操作系统申请空间 
    	struct LinkNode * temp = (struct LinkNode *)(malloc(sizeof(struct LinkNode)));
    	temp->index = nodeIndex;
    	temp->weight = weight;
    	temp->next = currentNode->next;
    	currentNode->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 * myArrayNode = &arrNode[startIndex];
    	struct LinkNode * node = myArrayNode->next;
    	
    	while(node != NULL)	
    	{
        
    		distance[node->index] = node->weight; //再次赋值 
    		node = node->next;
    	}
    }
    
    //Dijkstra算法 
    void Dijkstra()
    {
        
    	struct LinkNode * node; //临时变量 
    	int count = 0; //确定了最小距离的点的数量 
    	
    	//遍历每一个点 
    	while(count < size) //这样写代码，形式上与Prim算法高度一致 
    	//for(int i = 0; i < size; i++)	
    	{
        
    		int minIndex = 0;
    		int minDistance = inf;
    		
    		//在distance数组中，寻找距离原点距离的最小值，以及对应的点 
    		//可以用小顶堆进行优化，使寻找最小值的时间复杂度降低至O(logN) 
    		for(int j = 0; j < size; j++) 
    		{
        
    			if(book[j] == 0 && minDistance > distance[j])
    			{
        
    				minDistance = distance[j];
    				minIndex = j;
    			}
    		}
    		book[minIndex] = 1; //估计值变成确定值，标记有最小值的那个点被访问过 
    		count++;
    		
    		//这一段代码跟原始的Dijkstra算法不一样，效率变高了 
    		node = arrNode[minIndex].next;
    		while(node != NULL) //遍历链表上每一个结点
    		{
        
    			if(distance[node->index] > node->weight + minDistance) //更新distance数组
    			{
        
    				distance[node->index] = node->weight + minDistance;
    			}
    			node = node->next;
    		}
    	}	
    }
    
    //释放资源 
    void releaseResource()
    {
        
    	struct LinkNode * temp; 
    	for(int i = 0; i < size; i++) //释放数组中每个点的相邻结点
    	{
        
    		while(arrNode[i].next != NULL)
    		{
        
    			temp = arrNode[i].next; //用temp接手要删除的结点。 
    			arrNode[i].next = arrNode[i].next->next; //数组中的结点直接指向孙子结点
    			free(temp);//这时就可以free temp号结点了 
    		}
    	}
    }
    
    void show()
    {
        
    	//同上
    }
    
    int main()
    {
        
    	//插入数据 
    	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);
    	
    	initDistance(0);
    	
    	printf("初始状态：\r\n");
    	show();
    	
    	Dijkstra();
    	printf("用邻接表的Dijkstra算法计算之后：\r\n");
    	show();
    	
    	releaseResource(); //释放内存 
    	printf("Hello\r\n");
    	return 0;
    }

计算结果如下：

![在这里插入图片描述][20200722111746753.png]  
下一节，我们将使用邻接表和优先级队列对Dijkstra算法进行优化。

[20200722111746753.png]: /images/20230209/dee5dc64b0e74924b372a16d50dbae17.png