队列优化的Bellman-Ford算法 (C语言实现)

以你之姓@ 2023-03-01 05:39 3阅读 0赞

Bellman-Ford算法是比较暴力的，对着所有边一通猛算。当被计算的图是稠密图时,

![在这里插入图片描述][20200722115921182.png]  
所以时间复杂度为O(N \* M) = O(N^3)。这个时间复杂度是非常高的。那么有没有优雅、高效的计算方法呢？这就是本节要讨论的队列优化的Bellman-Ford算法。  
小伙伴，你应该还记得BFS算法 (广度优先算法) 中使用队列进行优化吧，其实队列优化的Bellman-Ford算法基本上就可以认为是BFS + Bellman-Ford算法，只不过这里的图是用邻接表实现的，而且BFS算法中，一个结点最多只能被加入队列一次，但这里可以被反复加入队列。下面我们就来看完整的代码：

#include <stdio.h>
    #include <stdlib.h>
    
    int n = 6; //顶点数 
    int m = 10; //边的数量 
    int inf = 999; //infinite 
    int distance[6]; //一维数组，记录距离 
    int book[6];
    int size = n;
    int queue [100]; //用队列优化Bellman算法
    int head = 0;//队列的头 
    int tail = 0;//队列的尾 
    
    //LinkNode是用于邻接表中，一个结点连接的其它结点。需要结点的编号、权重 
    struct LinkNode{
        
    	int index = 0;
    	int weight = 0;
    	struct LinkNode * next = NULL;
    };
    
    //声明结构体ArrayNode，用于邻接表中的数组 
    struct ArrayNode{
        
    	struct LinkNode * next = NULL;
    };
    
    //用一个数组存放首元素。每个首元素后面用指针连接各个结点 
    struct ArrayNode arrNode[6]; //这是地图 
    
    //distance数组的初始化。Bellman算法中的数组的初始化跟Dijkstra算法不一样，
    //这里只需要对起点设置为0，其它都设置为inf 
    void initDistance(int startIndex)
    {
        
    	for(int i = 0; i < size; i++) 
    	{
        
    		distance[i] = inf; //初始化，默认距离为infinite 
    	}
    	distance[startIndex] = 0; //原点为0 
    }
     
    //头插法，得到的结果的次序是反的是得到的结果的次序是反的 
    void addNode(int parentIndex, int nodeIndex, int weight)
    {
        
    	//与Dijkstra算法中的addNode函数相同 
    }
    
    void Bellman(int startIndex)
    {
        
    	queue[tail] = startIndex; //指定的点入列
    	tail++; //队列的尾巴+1 
    	book[startIndex] = 1; //标记已入列
    	
    	while(head < tail) //队列不为空就继续循环 
    	{
        
    		int currentIndex = queue[head]; //队列头 
    		struct ArrayNode myArrayNode = arrNode[currentIndex]; //链表的头 
    		struct LinkNode * myLinkNode = myArrayNode.next; //第一节链表 
    		
    		//printf("当前的结点: %d\r\n", currentIndex);
    		while(myLinkNode != NULL) //遍历每一节链表 
    		{
         
    			int linkIndex = myLinkNode->index; //一个结点的index
    			//printf("链表上的结点: %d\r\n", linkIndex);
    			
    			//如果从起点到linkIndex的距离可以更新为: 
    			//起点到链表头结点的距离 + 链表头结点到这一节链表的距离 
    			if(distance[linkIndex] > myLinkNode->weight + distance[currentIndex])
    			{
        
    				//printf("更新：%d => %d + %d\r\n", distance[linkIndex], myLinkNode->weight, distance[currentIndex]);
    				distance[linkIndex] = myLinkNode->weight + distance[currentIndex];
    				
    				//如果这一个结点还没有加入队列，就加入队列
    				//用一个book[]记录所有结点是否已经加入队列 
    				if(book[linkIndex] == 0)  
    				{
        
    					queue[tail] = linkIndex; //加入队列 
    					tail++; //队列的尾巴 + 1 
    					book[linkIndex] = 1; //加入队列后，修改book数组对应的值 
    				}
    			}
    			myLinkNode = myLinkNode->next; //访问下一个结点 
    		}
    		
    		book[queue[head]] = 0; //遍历队列首元素的所有子节点之后，首元素可能重新被访问，所以需要修改book数组对应的值 
    		head++; //队列头+1 
    		//printf("\r\n\r\n");
    	}
    }
    
    void show() //显示distance数组的值
    {
        
    	//与Dijkstra算法中的show函数相同
    }
    
    //释放资源 
    void releaseResource()
    {
        
    	//与Dijkstra算法中的releaseResource函数相同
    }
    
    void traverse(int parentIndex)
    {
        
    	//与Dijkstra算法中的traverse函数相同
    }
    
    void traverseAll()
    {
        
    	//与Dijkstra算法中的traverseAll函数相同
    }
    
    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);
    	
    	traverseAll(); //全部遍历
    
    	printf("初始状态：\r\n");
    	initDistance(0);
    	show(); //显示distance数组的值
    	
    	Bellman(startIndex);
    	printf("队列优化的Bellman-Ford算法运行结果：\r\n");
    	show(); //显示distance数组的值
    	releaseResource(); //释放资源 
    	return 0;
    }

运行结果：  
![在这里插入图片描述][20200722120047748.png]  
在随机数据的情况下，队列优化的Bellman-Ford算法的效率是很高的。而且跟原始的Bellman-Ford算法一样，它可以处理负权边的图。但是当被处理的图是稠密图，或者其它特殊情况时，队列优化的Bellman-Ford算法的时间复杂度也是O(M \* N)。不过从代码的复杂度来看，原始的Bellman-Ford算法和队列优化的Bellman-Ford算法的代码都是相对简单的。而Dijkstra算法就比较复杂了，尤其是堆优化的Dijkstra算法，确实是太复杂了。

[20200722115921182.png]: /images/20230209/a1d167564cae465fbdf91e324096d01c.png
[20200722120047748.png]: /images/20230209/f6c95650860245dab984099b0a04a4e0.png