无权图单源最短路径问题

墨蓝 2022-12-25 06:00 228阅读 0赞

## 一 概述 ##

无权图：即表示图中的边是没有权重的，或者是所有的边权重为同一个正数。

单源：以一个顶点为初始顶点出发，求解该顶点到其他顶点的最短路径。

最短路径：定义从顶点u到顶点v的最短路径d(u，v)为从u到v的任何路径中边数最少的路径。如果从某一顶点u到顶点v没有通路时，则d(u，v) = **∞。**

## 二 无权图单源最短路径问题求解过程 ##

先看一个问题：找到从顶点1到顶点5的路径

![20201130213854307.png][]

直观的可以发现图中的路径有1-2-5和1-2-4-5两条路径。其中最短路径为1-2-5。

根据广度优先算法中遍历的都是与初始结点较近的结点，所以可以利用这个性质来进行最短路径的查找。

**无权图单源最短路径问题的重要代码：**

void BFS_MIN_Distance(Graph G,int u){
    	for(int i = 0; i < G.vexnum; ++i){
            d[i] = MAX;//将初始顶到其他顶点之间的路径设置为MAX,即表示没有路径
        }
    	//将改顶点在辅助标记数组中的值设置为TRUE，表示该顶点已经被访问且入队
    	visited[u] = TRUE;
        d[u] = 0;//表示初始顶点到初始顶点的值0
    	//将该顶点入队
    	EnQueue(Q,u);
    	while(!isEmpty(Q)){
    		//出队队首元素，并将其赋值到v当中
    		Dequeue(Q,u);
    		//找到所有符合要求的邻接顶点
    		//FirstNeighbor求某个顶点的第一个邻接顶点，当此时的w为-1表示无邻接顶点，当w>0成立时，该w为邻接顶点的编号
    		//NextNeighbor求某个顶点的其他邻接顶点。
    		for(w = FirstNeighbor(G,u);w >= 0;w = NextNeighbor(G,u,w))
    			if(!visited[w]){
    				//将当被访问过的顶点标记为访问过
    				visited[w] = TRUE;
                    d[w] = d[u] + 1;//初始顶点到顶点w的最短路径，u到顶点的路径长度d[u]加上其到顶点w的一条边，即为最短路径
    				//将该顶点入队
    				EnQueue(Q,w);
    			}//if
    	}//while
    }

上述即为利用广度优先搜索算法的性质解决无权图单源最短路径的问题。

[20201130213854307.png]: /images/20221120/bd83ff7b94c94a298cd3eb9f10c597af.png