最短路径问题

“G港”是个物流集散中心，经常需要往各个城市运东西，怎么运送距离最近？

——单源最短路径问题

各个城市之间也需要互相往来，相互之间怎么走距离最近？

——每对顶点间的最短路径

BFS算法

 

注：无权图可以视为一种特殊的带权图，只是每条边的权值都为1

就是对BFS的小修改，在visit一个顶点时，修改

其最短路径长度d[]并在path[]记录前驱结点

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

//求顶点U到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int u){
    //d[i]表示从u到i结点的最短路径
    for(i = 0;i=0;w=NextNeighbor(G,u,w)){
            //检测v所有邻接点
            if(!visited[w]){            //w为v的尚未访问的邻接点
                d[w] = d[u]+1;          //路径长度加1
                path[w] = u;            //最短路径应从u到w
                visited[w] = true;      //对w做已访问标记
                EnQueue(Q,w);           //顶点w入队列
            }
        }
    }
}

Dijkstra算法

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

通过path[]可知，V0到V2的最短（带权）路径为：V2<——V1<——V4<——V0

时间复杂度：O(|푉|2)

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

 

Flotd算法

Floyd算法：求出每一对顶点之间的最短路径

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

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

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

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

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

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

…

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

时间复杂度：O(|푉|3)

空间复杂度：O(|푉|2)

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

注：也可用Dijkstra算法求所有顶点间的最短路径，重复|V|次即可，总的时间复杂度为：O(|푉|3)