东莞网站优化推广方案,大连开发区邮编,开发网站的技术路线,全国企业公示系统查询1 .单源最短路径
1.BFS算法(无权图)
使用广度优先遍历实现一个顶点到达其他所有顶点的最短路径。 注:无权图可以视为一种特殊的带权图#xff0c;只是每条边的权值都为1。
1.算法思路#xff1a;
定义一个数组存储每个结点与当前的结点的最短距离#xff0c;定义一个数组…1 .单源最短路径
1.BFS算法(无权图)
使用广度优先遍历实现一个顶点到达其他所有顶点的最短路径。 注:无权图可以视为一种特殊的带权图只是每条边的权值都为1。
1.算法思路
定义一个数组存储每个结点与当前的结点的最短距离定义一个数组存储当前结点的前驱结点序号。定义一个数组存储所有结点的访问情况已访问为true未访问为false。
2.代码实现
就是对BFS的小修改 在visit一个顶点时修改其最短路径长度d[]并在path[]记录前驱结点
//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u) {// d[i]表示从u到i结点的最短路径for (i 0; i G.vexnum; i) {d[i] o;//初始化路径长度path[i] -1;//最短路径从哪个顶点过来}d[u] 0;visited[u] TRUE;EnQueue(Q, u);while (!isEmpty(Q)) {// BFS算法主过程DeQueue(Q, u);//队头元素u出队for (w FirstNeighbor(G, u); w 0; w NextNeighbor(G, u, w))if (!visited[w]) {// w为u的尚未访问的邻接顶点d[w] d[u] 1;//路径长度加1path[w] u;//最短路径应从u到wvisited[w] TRUE;//设已访问标记EnQueue(Q, w);//顶点w入队}}
}由广度优先遍历生成的广度优先生成树一定是高度最小的生成树。
2.Dijkstra迪杰斯特拉算法带权图、无权图)
1.分析BFS算的局限性 BFS算法求单源最短路径只适用于无权图或所有边的权值都相同的图。
回顾知识点
带权路径长度当图是带权图时一条路径上所有边的权值之和称为该路径的带权路径长度。
2.算法分析
第一个数组标记各顶点是否已找到最短路径存放true或者false。第二个数组记录各顶点的最短路径长度无穷代表暂没找到最短路径。第三个数组记录各个结点最短路径上的直接前驱。
3.算法步骤
第1轮︰循环遍历所有结点找到还没确定最短路径且dist最小的顶点Vi,令final[i]ture。检查所有邻接自V的顶点若其final值为false,则更新dist和 path 信息。第2轮:循环遍历所有结点找到还没确定最短路径且dist最小的顶点Vi,令final[i]ture。检查所有邻接自V的顶点若其final值为false,则更新dist和path 信息。直到最后一轮:循环遍历所有结点找到还没确定最短路径且dist最小的顶点Vi令final[i]ture。
4.算法实现
初始:若从Vo开始令final[0]ture; dist[0]O; path[0]-1。其余顶点final[k]false;dist[k]arcs[0][k]; path[k] (arcs[O][k]co) ? -1:0。n-1轮处理∶循环遍历所有顶点找到还没确定最短路径且dist最小的顶点V令finali]ture。并检查所有邻接自Vi的顶点对于邻接自Vi的顶点V若final[i]false且dist[i]arcs[i]i] dist[i]则令dist[i]dist[i]arcs[i]lil; path[i]i。(注: arcs[们]表示V到V%的弧的权值)
某个结点到其他结点的最短路径的时间复杂度为O(N2)即O(|V|2) 也可用Dijkstra算法求所有顶点间的最短路径重复V次即可总的时间复杂度也是OIV|3).
5.用于带负权值带权图
结论:Dijkstra算法不适用于有负权值的带权图。
2.各顶点间的最短路径
1.Floyd算法带权图、无权图)
Floyd算法:求出每一对顶点之间的最短路径。
1.算法思想 使用动态规划思想将问题的求解分为多个阶段:
对于n个顶点的图G求任意一对顶点Vi-Vj之间的最短路径可分为如下几个阶段:#初始︰不允许在其他顶点中转最短路径是?#O:若允许在Vo中转最短路径是?#1∶若允许在Vo、V中转最短路径是?#2:若允许在Vo、V1、V2中转最短路径是?#n-1:若允许在Vo、V1、V2… Vn-1中转最短路径是?
2.算法实现
定义一个二维数组A相当于图的邻接矩阵存储每个顶点之间的最短路径定义一个二维数组path存储A位置对应路径需要经过的中转顶点。使用动态规划逐渐增加可以中转顶点个数更新两个二维数组的信息。
3 .代码实现 时间复杂度O(IVl3) 空间复杂度O(IV|2) // ......准备工作根据图的信息初始化矩阵A和path (如上图)for (int k 0; k n; k) {//考虑以vk 作为中转点for (int i 0; i n; i) {//遍历整个矩阵i为行号j为列号for (int j 0; j n; j) {if (A[i][j] A[i][k] A[k][j]) {//以Vk 为中转点的路径更短A[i][j] A[i][k] A[k][j];//更新最短路径长度path[i][j] k; //中转点}}}}4.Floyd算法可以用于负值带权图
Floyd算法不能解决带有“负权回路”的图有负权值的边组成回路)这种图有可能没有最短路径。
3.三种算法的比较
BFS 算法Dijkstra算法Floyd 算法无权图√√√带权图x√√带负权值的图xxx带负权回路的图xxx时间复杂度O(V2)或O(VE)O(V2O(V3 通常用于求无权图的单源最短路径求带权图的单源最短路径求带权图中各顶点间的最短路径
