【数据结构】最短路径问题—BFS算法、Dijkstra算法、Floyd算法

1. BFS算法

【数据结构】图的遍历—广度优先遍历、深度优先遍历

最短路径问题，在我们之前讲到的广度优先遍历基础上做了一些改造。

BFS算法求单源最短路径只适用于无权图，或所有边的权值相同的图。

无向图可以看成一个特殊的有向图，只不过每个路径长度都为1。

bool visited[MAX_VERTEX_NUM];  // 访问标记数组，初始都为false

// 广度优先遍历
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[v]=true;  // 对v做已访问标记
    Enqueue(Q,v);  // 顶点u入队列Q
    while(!isEmpty(Q)){  //  BFS算法主过程
        DeQueue(Q,u);  // 顶点u出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
            if(!visited[w]){  //  w为u的尚未访问的邻接顶点
                d[w]=d[u]+1;  // 路劲长度加1
                path[w]=u;  // 最短路径应从u到w
                visited[w]=true;  // 对w做已访问标记
                EnQueue(Q,w);  // 顶点w入队列
            }
        }
    }
}

从顶点2开始的执行过程。

d[]数组记录了距离起始地点的路径长度。path[]记录了当前结点的上一个结点值。visited从刚开始的false变为了true，表示每个结点都被访问过了。

改造：

如果我们使用BFS广度优先生成树，在visit一个顶点时，d[]数组记录了距离起始地点的路径长度。path[]记录了当前结点的上前驱结点。

2到8的最短路径长度=d[8]=3.

通过path数组可知，2到8的最短路径为：2 -> 6 -> 7 -> 8。

2. Dijkstra算法

1. 有权图最短路径

从V0出发，求出V0到各个结点的最短路径。

V0到V2的最短（带权）路径长度为：dist[2]=9。

通过path[]可知，V0到V2的最短（带权）路径：V0 -> V4 -> V1 -> V2。

2. 复杂度分析

初始：若从V0开始，令final[0]=true;dist[0]=0;path[0]=-1。 其余顶点final[k]=false;dist[k]=arcs[0][k];path[k]=(arcs[0][k]==∞)?-1:0

n-1轮处理：循环遍历所有结点，找到还没确定最短路径，且dist最小的顶点Vi，令final[i]=true。并检查所有邻接自Vi的顶点，对于邻接自Vi的顶点Vj，若final[j]==false且dist[i]+arcs[i][j]<dist[j]，则令dist[j]=dist[i]+arcs[i][j];path[j]=i。（注：arcs[i][j]表示Vi到Vj的弧的权值）

Dijkstra算法不适用于有负权值的带权图。

3. Floyd算法

1. Floyd算法

求出每一对顶点之间的最短路径。

使用动态规划思想，将问题的求解分为多个阶段。

对于n个顶点的图G，求任意一对顶点Vi -> Vj之间的最短路径可分为如下几个阶段：

#初始：不允许在其他顶点中转，最短路径是？

#0：若允许在V0中转，最短路径是？

#1：若允许在V0，V1中转，最短路径是？

#2：若允许在V0，V1，V2中转，最短路径是？

……

#n-1：若允许在V0，V1，V2……Vn-1中转，最短路径是？

2. 核心代码

// ……准备工作，根据图的信息初始化矩阵A和path
for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){  // 考虑以 v k 作为中转点
        for(int j=0;j<n;j++){  // 遍历整个矩阵，i为行号，j为列号
            if(A[i][j]>A[i][k]+A[k][j]){  // 以v k为中转点的路径最短
                A[i][j]=A[i][k]+A[k][j];  // 更新最短路径长度
                path[i][j]=k;  // 中转点
            }
        }
    }
}

Floyd算法可以用于负权值带权图。

Floyd算法不能解决带有“负权回路”的图〈有负权值的边组成回路)，这种图有可能没有最短路径。

4. 小结