肥城网站建设广州外地车牌,wordpress 伪原创 插件,多用户智能网站建设源码,wordpress 繁体语言包之前文章对于Dijkstra算法进行了讲解和实现#xff0c;其实现的原理在于采用贪心算法#xff0c;遍历N(结点数)次#xff0c;每次找到局部最优的路径的结点u#xff0c;判断该节点可达的顶点v的权重是否大于结点u权重u-v的权重#xff0c;如果大于则替换顶点v的权重(也…之前文章对于Dijkstra算法进行了讲解和实现其实现的原理在于采用贪心算法遍历N(结点数)次每次找到局部最优的路径的结点u判断该节点可达的顶点v的权重是否大于结点u权重u-v的权重如果大于则替换顶点v的权重(也叫松弛操作)。因为Dijkstra算法无法正确计算负权路径的最短路径(详情可看上一节)所以有了Bellman-Ford算法来解决这一问题。相关文章图论-图的构建深度优先搜索遍历图广度优先搜索遍历图单源最短路径之Dijkstra算法贪心算法如何贪心贝尔曼-福特算法贝尔曼-福特算法(Bellman-Ford)是由理查德·贝尔曼(Richard Bellman) 和 莱斯特·福特 创立的求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作(V是顶点数量)得到所有可能的最短路径。其优于Dijkstra算法的方面是边的权值可以为负数、实现简单缺点是时间复杂度过高高达O(VE)。但算法可以进行若干种优化提高了效率。贝尔曼-福特算法与迪科斯彻算法类似都以松弛操作为基础即估计的最短路径值渐渐地被更加准确的值替代直至得到最优解。在两个算法中计算时每个边之间的估计距离值都比真实值大并且被新找到路径的最小长度替代。 然而迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点然后对其出边进行松弛操作而贝尔曼-福特算法简单的对所有边进行松弛操作共V-1次其中V是图的顶点数量。在重复地计算中已计算得到正确的距离的边的数量不断增加直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入实现过程从上面介绍我们可以知道Bellman算法对每一条边采用松弛操作对于单源最短路径实现来说源点到某一顶点所经过的边最多为V-1条(可以看成树的两个结点)如下三个顶点ABCA-C最多走过2两条边即A-B-CA-BA-CB-C在我们将源点最短路径设置为0时每次松弛操作**至少会松弛一条边**而最多共有N-1条边所以我们需要遍历N-1次。每一次遍历的松弛操作和Dijkstra算法类似判断结点u权重是否大于 v-u的权重v的权重。与Dijkstra算法使用最短边向其他顶点扩展方案不同在Bellman-Ford算法中松弛操作是针对边其目的是对每一条边进行松弛这样总能使得边达到最小如下图解A为源点A-C 2D-C 1A-B -1B-D 1 上面共计 4个顶点源点A到达任意顶点BCD最高走V-13条边也就是松弛3轮初始化时源点A到任意顶点设置为无穷大s[]表示最短距离S[A]0。那么第一轮:A - C 边权2 可以推导 (S[C] ∞) (S[A] W[AB] 02)条件符合所以进行松弛操作 S[C] 2D - C 边权1 可以推导 (S[C] 2) (S[D] W[DC] ∞1)条件不符合无法进行松弛操作 A - B 边权-1 可以推导 (S[B] ∞) (S[A] W[AB] 0(-1))条件符合所以进行松弛操作 S[B] -1B - D 边权1 可以推导 (S[D] ∞) (S[B] W[BD] -11)条件符合所以进行松弛操作 S[D] 0然后进行第二轮(基于第一轮): A - C 边权2 可以推导 (S[C] 2) (S[A] W[AB] 02)条件不符合无法进行松弛操作 D - C 边权1 可以推导 (S[C] 2) (S[D] W[DC] 01)条件符合所以进行松弛操作 S[C] 1A - B 边权-1 可以推导 (S[B] -1) (S[A] W[AB] 0(-1))条件不符合无法进行松弛操作 B - D 边权1 可以推导 (S[D] 0) (S[B] W[BD] -11)条件不符合无法进行松弛操作 第三轮逻辑同上。我们会发现其实第二轮的时候已经实现最短路径了第三轮属于没有用的遍历。负环负环,又叫负权回路,负权环,指的是一个图中存在一个环,里面包含的边的边权总和0。在存在负环的图中,是求不出最短路径的因为每次要在这个环上遍历最短路径就会无限次的变小。如下A-B 1A-C 1C-B -1B-D 1D-C 1那么BCD就会存在负环按照上面N-1次遍历后我们再遍历最短路径仍会变小。实现代码(C) main.cpp// Bellman-Ford Created by 陈龙.// Copyright © 2019 陈龙. All rights reserved.//#include using namespace std;//顶点和边和源点int N,E,S; struct Graph{ //起点终点 int u,v; int w;// Graph(int _u,int _v,int _w):u(_u),v(_v),w(_w){};};int main(int argc, const char * argv[]) { // insert code here... cinNES; Graph g[N]; int dis[N]; int u,v,w; for (int i0; iuvw; g[i].u u; g[i].vv; g[i].ww; } //初始化 dis[S] 0; for(int i0;i g[j].w dis[g[j].u]) { dis[g[j].v] g[j].w dis[g[j].u]; } } } // 判断是否有负环路 for(int i0; i dis[g[i].u] g[i].w){ cout
