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矩阵递归地找到完整路径。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)