(48)王道数据结构-最短路径问题(BFS)

基本概念

广度优先搜索查找最短路径只是对无权图而言的。图是带权图时，把从一个顶点v0到图中其余任意一个顶点vi的一条路径(可能不止一条)所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最短的那条路径称为最短路径。

单源最短路径

求解最短路径的算法通常都依赖于一种性质，即两点之间的最短路径也包含了路径上其他顶点间的最短路径。带权有向图G的最短路径问题一般可分为两类：一是单源最短路径，即求图中某一顶点到其他各顶点的最短路径，可通过经典的Dijkstra 算法求解；二是求每对顶点间的最短路径，可通过Floyd-Warshall算法来求解。

bool visited[MAX_VERTEX_NUM]; //访问标记数组
//广度优先遍历
void BFS(Graph G, int v) {//从顶点v出发，广度优先遍历图G
    visit(v); //访问初始顶点v
    visited[v]=TRUE; //对v做已访问标记
    Enqueue(Q,v); //顶点v入队列Q
    while(!isEmpty(Q)) {
        DeQueue(Q,v); //顶点v出队列
        for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)) {//检测v所有邻接点
            if(!visited[w]) { //w为v的尚未访问的邻接顶点
                 visit(w); //访问顶点w
                 visited[w]=TRUE; //对w做已访问标记
                 EnQueue(Q,w); //顶点w入队列
            }
        }  
    }
}

顶点到顶点

代码逻辑

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u) {
    //d[i]表示从u到i结点的最短路径
    for(i=0; i<G.vexnum; ++i) {
        d[i]=∞; //初始化路径长度
        path[i]=-1; //最短路径从哪个顶点过来
    }
    d[u]=0;
    visited[u]=TRUE;
    EnQueue(Q,u);
    while(!isEmpty(Q)) { //BFS算法主过程
        DeQueue(Q,u); //队头元素u出队
        for(w=FirstNeighbor(G,u); w>=0; w=NextNeighbor(G,u,w)) {
            if(!visited[w]) {//w为u的尚未访问的邻接顶点
                d[w]=d[u]+1; //路径长度加1
                path[w]=u; //最短路径应从u到w
                visited[w]=TRUE; //设已访问标记
                EnQueue(Q,w); //顶点w入队
            }
        }   
    }
}