数据结构笔记chapter06

1. BFS算法

2. Dijkstra算法

3. Floyd算法

最短路径问题：

（1）单源最短路径问题：BFS算法（无权图）、Dijkstra算法（带权图、无权图）

（2）每对顶点间的最短路径： Floyd算法（ 带权 图、无权图）

1. BFS算法：求⽆权图的单源最短路径

（1）⽆权图可以视为⼀种特殊的带权图，只是每条边的权值都为1

（2）代码实现

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int u){
    
    //d[i]表示从u结点到i结点的最短路径
    for(i=0;i=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入队
           }//if
    }//while
}

就是对BFS的⼩修改，在visit⼀个顶点时，修改 其最短路径⻓度 d[ ] 并在 path[ ] 记录前驱结点

（3）与⼴度优先⽣成树关系：

⼀定是以该结点为根的，高度最小的生成树

---

2. Dijkstra算法

Dijkstra：

 （1）BFS的局限性

带权路径长度——当图是带权图时，⼀条路径上所有边的权值之和，称为该路径的带权路径长度

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

（2）算法实现

final数组：标记各顶点是否已找到最短路径：TRUE或者FALSE

dist数组：最短路径⻓度；初值为到v0的路径长度

path数组：路径上的前驱

第1轮：

step1：循环遍历所有结点，找到还没确定最短路径（FALSE），且dist 最小的顶点Vi，令final[i]=TRUE。

step2：检查所有邻接⾃ Vi 的顶点，若其 final 值为false， 则更新 dist 和 path 信息

第2轮：

循环遍历所有结点，找到还没确定最短 路径，且dist 最⼩的顶点Vi，令final[i]=ture

检查所有邻接⾃ Vi 的顶点，若其 final 值为false， 则更新 dist 和 path 信息

...

n-1轮处理：

循环遍历所有顶点，找到还没确定最短路径，且dist 最⼩的顶点Vi，令final[i]=ture。

并检查所 有邻接⾃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 的弧的权值）

（3）每一轮时间复杂度O(2n)=O（n）

总时间复杂度 O(n2)，即O(|V|^2)

（4）局限

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

---

3. Floyd算法（Floyd-Warshall算法 ）

1.Floyd：

Floyd算法：Floyd算法可以⽤于负权值带权图；不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径，走越多路径越小。

堆排序算法

2. Floyd算法

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

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

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

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

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

...

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

即，每次新增考虑中转点

设置A存储两点之间的最短路径，设置path存储中转点信息，初始为A^（-1）,path^(-1)

 

//Floyd核心代码
for(int k=0;kA[i][k]+A[k][j]){  //以V_k为中转点的路径更短
                
                A[i][j]=A[i][k]+A[k][j];   更新最短路径长度
                path[i][j]=k;   //中转点
            }
        }
    }
}

时间复杂度：O(|V|^3)

空间复杂度：O(|V|^2)

最终，通过path矩阵递归地找到完整路径。