宁波正规品牌网站设计,设计公司logo需要注意什么,校园网络建设方案设计,wordpress 授权协议算法概述#xff1a; Bellman-Ford算法核心代码如下 for(int i 1;in-1;i) for(int j 1;jm;j) if(dic[v[j]] dic[u[j]] w[j]] dic[v[j]] dic[u[j]] w[j]; 首先我们要了解一个点就是我们这次不再使用邻接矩阵来存储图的信息#xff0c;而是定义三个一维数组来…算法概述 Bellman-Ford算法核心代码如下 for(int i 1;in-1;i) for(int j 1;jm;j) if(dic[v[j]] dic[u[j]] w[j]] dic[v[j]] dic[u[j]] w[j]; 首先我们要了解一个点就是我们这次不再使用邻接矩阵来存储图的信息而是定义三个一维数组来存储图的信息。 首先定义 u[n] 来存储边的起点v[n]来存储边的终点w[n]来存储边的长权重。 例如存储如下元素 4 4 1 2 3 2 4 7 3 4 5 3 1 3 和Dijkstra算法一样这段代码也是求单源最短路径所以我们同样也要定义一个dic[n]数组来存储所有点到1的最短距离。注意这里因为使用的并非邻接矩阵所以初始化dic时默认除了dic[1] 0以外暂时全部看作不连通也就是假设以以上数据为例dic内容要初始化为
【0 inf, inf, inf】,其中inf看作无穷大表示不通。 那么我们再来看核心代码的最后两句。 if(dic[v[j]] dic[u[j]] w[j]] dic[v[j]] dic[u[j]] w[j]; dic[v[j]]的值是1 到 v[j]这个点的值 dic[u[j]] 是 1 到 u[j] 这个点的值 w[j] 是 u[j] 到 v[j] 的值意思是如果如果 1 通过 1 - u[j] - v[j] 这条路比 1 - v[j] 值小的话更新dic[v[j]]的值。也就是通过u[j] -v[j] 这条边进行松弛来优化路径。 初始化示意图如下 for(int i 1;in-1;i) for(int j 1;jm;j) if(dic[v[j]] dic[u[j]] w[j]] dic[v[j]] dic[u[j]] w[j]; 当第一轮循环时:
当先通过 j 1 通过第一条边进行优化时 if(dic[ 2 ] dic[ 1 ] 3]发现dic[2 ] 需优化然后
重置 dic[2] dic[1]3 3。
当 j 2 时 通过第二条边进行优化时 if(dic[ 4 ] dic[ 2 ] 7],发现dic[4] 可以优化然后
重置 dic[ 4 ] dic[ 2 ] 7 37 10。
当 j 3时通过第三条边进行优化时if(dic[ 4 ] dic[ 3 ] 5]发现dic[4]无法优化因为
dic[ 4 ] 10 dic[ 3 ] 5 inf 5。 当 j 4 时 通过第四条边进行优化时 if(dic[ 1 ] dic[ 3 ] 3],发现dic[1]无法优化因为
dic[ 1 ] 0 dic[ 3 ] 3 inf 3。
最后经过一轮松弛后得到 dic [0, 3, inf ,10]; 当 i 2 进行第二轮松弛时 当先通过 j 1 通过第一条边进行优化时 if(dic[ 2 ] dic[ 1 ] 3]发现dic[2 ] 无需优化因为 dic[2] dic[1]3 3。
当 j 2 时 通过第二条边进行优化时 if(dic[ 4 ] dic[ 2 ] 7],发现dic[4] 无需优化
当 j 3时通过第三条边进行优化时if(dic[ 4 ] dic[ 3 ] 5]发现dic[4]无需优化
当 j 4 时 通过第四条边进行优化时 if(dic[ 1 ] dic[ 3 ] 3],发现dic[1]无需优化
这样我们就完成了这组数据因为这是构建的有向图所以1 才无法到达 3.
既然很清晰流程了 我再丢给大家一组数据
5 7 1 2 8 1 3 1 1 4 2 3 4 2 2 4 3 3 5 3 4 5 3 现在请找到一张草稿纸来试着执行刚才所讲的流程。 具体代码 #includestdio.h int main(void) { int u[10], v[10], w[10]; int n, m, inf 99999999; int dic[10] { 0 }; scanf_s(%d%d, n, m); for (int i 1; i m; i) scanf_s(%d%d%d, u[i], v[i], w[i]);//存储边的信息 for (int i 2; i n; i) dic[i] inf;//初始化1 的单源最短路径值。
//核心代码 for (int i 1; i n - 1; i) for (int j 1; j m; j) if (dic[v[j]] dic[u[j]] w[j]) dic[v[j]] dic[u[j]] w[j]; for (int i 1; i n; i) printf(%d , dic[i]);//输出结果} 注意事项 最外层代码循环n-1次的原因是n 个顶点1到任何顶点的最多经过n-1个顶点。每一轮松弛循环如果没有完成单源最短路径的最终结果都至少会有一次松弛。 细心的同学可能会发现我们刚才使用的数据 5 7 1 2 8 1 3 1 1 4 2 3 4 2 2 4 3 3 5 3 4 5 3 是上一篇文章的内容在上一篇中结果是0 5 1 2 4 。
而在这里答案是0 8 1 2 4。 那么为什么会造成这种影响呢因为我们使用的这段代码是处理有向图的而在上一篇文章中是处理无向图的那么有没有什么办法来改进这段代码使代码能够处理无向图呢答案当然是可以的而且十分简单。 聪明的同学注意到数据 4 4 1 2 3 2 4 7 3 4 5 3 1 3 在第二轮就能发现没有优化证明已经得出结果每必要进行n-1轮循环那么大家思考下怎么提前退出循环呢
课后作业 改进这段代码使代码能够处理无向图。 如何证明达到最优解提前退出循环。 明天带来答案。
