6.4.2_2最短路径算法-Dijkstra算法

迪杰斯特拉

膜拜大佬大佬大佬大佬。。。。。。。。。

BFS算法的局限性：

BFS算法求最小路径长度不适用于带权值的图，如下图中的从G港出发根据BFS算法会计算R城的路径长度为10和P城的路径长度为5，但是实际G港->P城->R城距离为7这才是最短路径

带权路径长度(简称为路径长度)：一条路径上的所有边的权值之和

 

Dijkstra算法：

从单源顶点V0开始，以有向图为例

过程：

初始化：初始化三个数组，final[]数组用来记录单源顶点到各顶点是否找到了最短路径，V0是起点，所以开始final[V0]=true，d其他顶点final值都设为false。dist[]数组表示目前能找到的最短路径长度，设置能从图上显而易见的最短路径长度。V0->V0最短路径长度为0，dist[0]=0,V0->V1，根据图V0和V1直接相连且权值为10，即初始化的时候dist[V1]=10，V0到V2没有直接相连的边，所以目前V0到V2没有最短路径，即dist[V2]=∞，V0到V3同dist[V3]=∞，V0到V4直接相连的边的权值为5即目前V0单源到V4最短路径为dist[4]=5，path[]数组用来记录每个顶点在最短路径上的直接前驱，设置从图上能显而易见得到的最短路径的直接前驱。path[0]=-1。开始已经知道V0->V1即目前能找到的一条路是从V0过来的，所以path[1]=0表示目前能找到的最短的一条路径是从V0->V1，V4同目前能确定的一条比较好的路径也是从V0>V4，即path[4]=0

第一轮：找final中值为false的即还没找到最短路径的节点+dist中最短路径长度最小的顶点(就是找final中值为false的且dist中数值最小的，把这个顶点的final设为true就行了)，明显是V4(V1-V4都没确定最端路径长度，V1-V4dist最小的值为5，即dist[4]=5)然后把final[4]=true表示顶点4已找到最短路径且4的直接前驱是V0即path[4]=0，然后修改其他没有确定最短路径长度的顶点的dist和path值，没加入V4前V0->V1路径长度为10且path[1]=0，加入了V4之后有V0->V4->V1即5+3=8,10>8即V0到V4的最短路径为8，最短路径中V1的直接前驱为V4，即修改dis[1]=8，path[1]=4，同理修改V0->V2的dist和path，加入V4后有V0->V4->V2即5+9=14即修改dist[2]=14,path[2]=4,V0->V4->V3即5+2=7，dist[3]=7,path[3]=4

第2轮：找final中值为false的且dist中数值最小的顶点，把这个顶点的final，明显是V3(V1-V3都没确定最端路径长度，V1-V3dist最小的值为7，即dist[3]=7)然后把final[3]=true表示顶点3已找到最短路径且3的直接前驱是V0即path[3]=4，然后修改其他没有确定最短路径长度的顶点的dist和path值即修改V1和V2，没加入V3前V0->V4->V2最短路径长度为14，加入了V3之后有V0->V4->V3->V2即5+2+6=13,13<14即V0到V2的最短路径为13，最短路径中V2的直接前驱为V3，即修改dis[2]=13，path[2]=3，V1没找到不用修改

第3轮：找final中值为false的且dist中数值最小的顶点，把这个顶点的final，明显是V1(V1-V2都没确定最端路径长度，V1-V2dist最小的值为8，即dist[1]=8)然后把final[1]=true表示顶点1已找到最短路径且1的直接前驱是V0即path[1]=4，然后修改其他没有确定最短路径长度的顶点的dist和path值即修改V2，没加入V1前V0->V4->V3->V2最短路径长度为13，加入了V1之后有V0->V4->V1->V2即5+3+1=9,9<13即V0到V2的最短路径为9，最短路径中V2的直接前驱为V1，即修改dis[2]=9，path[2]=1

第3轮：找final中值为false的且dist中数值最小的顶点，把这个顶点的final，明显是V2(就剩下V2了)然后把final[2]=true表示顶点2已找到最短路径且2的直接前驱是V1即path[2]=1，然后修改其他没有确定最短路径长度的顶点的dist和path值发现final数组值都为true都确定了结束

找V2顶点最短路径长度+路径顶点序列：

最短路径长度看dist，dist[2]=9即V2最短路径长度为9

最短路径长度顶点序列看path，即从当前顶点找直接前驱直到找到path值为单源的这一串序列即为最短路径长度序列，path[2]=1即直接前驱为V1，path[1]=4即V1直接前驱为V4，path[4]=0即V4直接前驱为V0结束(因为单源节点是V0)，再左朝向即可如下：

V2 ← V1← V4← V0

 

Dijkstra算法时间复杂度：

 和普利姆算法相似，时间复杂度都是O(v²)（考试不考理解吧，背过就行了吧。。。。。。。）

 用于负权值带权图：

迪杰斯特拉算法用于带负值的带权图求最小路径时可能失效

如下所示：从V0出发，根据迪杰斯特拉算法，开始final中V1和V2值为false且dist[2]长度最小于是先确定V2的最小路径长度，设置final[2]=true，path[2]=0,dist[2]=7，再修改没确定最短长度的V1，改不了目前10就是V1的最短路径长度，于是确定V1，设置final[1]=true，path[1]=0,dist[1]=10然后没有可确定的顶点了算法结束，但是实际上V0->V2的最短长度应为V0->V1->V2即10-5=5，这个比目前迪杰斯特拉算法计算出的最短路径长度10要小，于是迪杰斯特拉算法失效

 

。。。。。。。。。。。。。。。