网络销售怎么做自己的网站,网页设计专业学校,免费php网站系统,wordpress 下载工具介绍
对于网图来说#xff0c;最短路径是指两顶点之间经过的边上权值之和最少的路径#xff0c;其路径上第一个点记为源点#xff0c;最后一个为终点。
计算最短路径有两个经典算法#xff0c;即迪杰斯特拉#xff08;Dijkstra#xff09;算法与弗洛伊德#xff08;Fl…介绍
对于网图来说最短路径是指两顶点之间经过的边上权值之和最少的路径其路径上第一个点记为源点最后一个为终点。
计算最短路径有两个经典算法即迪杰斯特拉Dijkstra算法与弗洛伊德Floyd算法。
Dijkstra算法
这个算法是从一个给定的顶点出发不断计算更新此顶点到目标顶点的最短路径
假如有这样一张网图 如果我们要求顶点0到顶点1的最短距离那无疑是1。由于1还与23相连所以我们也可以求出0-1-2的距离为1230-1-3距离为145
但如果求从顶点0到顶点2的最短距离由于边上都有权值5是大于3的所以0到2的最短距离是3
同时因为2与3,4相连我们可以求得由此路径的0-1-2-3314,0-1-2-4的距离为447而这条路径上0到3的距离要小于上述0-1-3那条则目前0到3的最短距离更新为4
... ...以此类推不断基于已经求出的中途的最短距离来更新到目标顶点的最短路径这就是这个算法的核心思想
具体代码实现 typedef struct{int vex[max];//顶点数组int arc[max][max];//带权边长int numN,numE;//顶点数及边数
}Mgraph;//用邻接矩阵存储整张图
int p[max];//储存最短路径下标数组
int d[max];//储存到各点的最短路径权值和
void SPDijkstra(Mgraph g,int v0){//传入图与起始顶点int m;int final[max];//记录从v0到i顶点的最短路径for (int i0;ig.numN;i){final[i]0;//初始化未未知最短路径的状态d[i]g.arc[v0][i];//将所有与v0有连线的加上权值p[i]-1;//初始化路径数组为-1}d[v0]0;//v0至v0距离为0final[v0]1;//标记v0至v0不需要求路径int k;for (int i1;ig.numN;i){//从v1开始找起mINT_MAX;for (int j0;jg.numN;j){if (!final[j]d[j]m){md[j];kj;//记录距v0最短的带权路径顶点}}final[k]1;//标记此顶点//开始更新最短距离for (int j0;jg.numN;j){if (!final[j]mg.arc[k][j]d[j]){d[j]mg.arc[k][j];//更新v0到j的最短路径p[j]k;//v0到j顶点的最短路径前驱是k}}}
}
Floyd算法 还是以此图为例
弗洛伊德算法常用于求取所有顶点至所有顶点的最短路径它利用动态规划的方法将顶点至顶点间的最短路径记录在一个二维数组中
在带权的邻接矩阵中arc[i][j]记录的为i j之间的距离如例图中arc[0][2]5
但如果找一个与两个顶点都相连的中间节点如1计算得出arc[0][1]arc[1][2]123这个值是小于5的这条路径的距离就可以更新到矩阵中代替5的位置
利用这种算法进行重复迭代对于每一对顶点i,j遍历所有的中间节点k检查是否存在一条路径比当前更短如果是则更新矩阵中的最短距离。这样就可以的出两个个顶点之间的最短路径与最短距离。
代码实现如下
int p[max][max];//p数组记录路径方便后续输出最短路径
int d[max][max];//记录最短距离
void SPFloyd(Mgraph g){for (int i0;ig.numN;i){for (int j0;jg.numN;j){d[i][j]g.arc[i][j];//初始化为邻接矩阵p[i][j]j;//初始化路径数组}}for(int k0;kg.numN;k){for (int i0;ig.numN;i){for (int j0;jg.numN;j){if(d[i][j]d[i][k]d[k][j]){d[i][j]d[i][k]d[k][j];//更新最短距离p[i][j]p[i][k];//更新路径即要到j的最短路径中j之前一个顶点为k}}}}
}
