查询网站收录情况的方法,asp网站制作成品作业,五寨网站建设,微平台文章目录一、综述二、图论最短路问题三、几个简单的作图方法四、Dijkstra#xff08;迪杰斯特拉#xff09;算法五、Bellman-Ford算法六、总结一、综述
本文主要根据图论的基本概念#xff0c;介绍图论中常见的建模问题——最短路问题。同时#xff0c;介绍了解决图论最短…
文章目录一、综述二、图论最短路问题三、几个简单的作图方法四、Dijkstra迪杰斯特拉算法五、Bellman-Ford算法六、总结一、综述
本文主要根据图论的基本概念介绍图论中常见的建模问题——最短路问题。同时介绍了解决图论最短路问题的两种算法Dijkstra迪杰斯特拉算法和Bellman-Ford贝尔曼-福特算法。
在此之前需要具备基本的图论知识哦~~~
二、图论最短路问题
图论最短路问题指的是在带权重的图中求出一条从一点节点到另一个节点的路径使这条路径上的权重之和最小。
三、几个简单的作图方法
1.CS Academy https://csacademy.com/app/graph_editor/ 2. Matlab 无向图graph()函数 有向图digraph()函数
四、Dijkstra迪杰斯特拉算法 DijkstraDijkstraDijkstra迪杰斯特拉算法描述 假设未选取的节点集合未V已选取的节点集合为S。 -除起点外其他节点初始距离为 ∞\infty∞起点距离为0。 -更新节点之间的距离相邻接的节点距离即为权值不相邻接的节点距离仍为 ∞\infty∞。 -选取另一个未被选取过且距离最小的节点作为中转点更新距离。原距离 该节点和目标节点的权值 目标节点的原距离则更新目标节点的距离为前者否则不更新。 -重复第三步直到到达目标节点。 下面来看一个例子 有一个旅行者想要从 v1v1v1 节点到 v8v8v8 求出最短旅行路线。 解决步骤 第一步初始化表格 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1000000000距离inf\infinfinf\infinfinf\infinfinf\infinfinf\infinfinf\infinfinf\infinfinf\infinfinf\infinf父亲节点-1-1-1-1-1-1-1-1-1第二步从 v1 节点开始 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1100000000距离0inf\infinfinf\infinfinf\infinfinf\infinfinf\infinfinf\infinfinf\infinfinf\infinf父亲节点v1-1-1-1-1-1-1-1-1第三步更新从 v1 可到达的节点的距离 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1100000000距离0631inf\infinfinf\infinfinf\infinfinf\infinfinf\infinf父亲节点v1v1v1v1-1-1-1-1-1第四步取距离最小的节点 v4 作为中转点更新从 v4 可到达的节点标号注意比较与原距离的大小 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1100100000距离0631inf\infinfinf\infinfinf\infinfinf\infinfinf\infinf父亲节点v1v1v1v1-1-1-1-1-1第五步更新后的结果 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1100100000距离0631inf\infinf11inf\infinfinf\infinfinf\infinf父亲节点v1v1v1v1-1v4-1-1-1第六步再取距离最小的节点 v3 作为中转点更新从 v3 可到达的节点标号注意比较与原距离的大小 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1101100000距离0631inf\infinf11inf\infinfinf\infinfinf\infinf父亲节点v1v1v1v1-1v4-1-1-1第七步更新后的结果由于3 2v3 到 v2 的距离 5 6因此更新 v2 列的距离 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1101100000距离0531inf\infinf11inf\infinfinf\infinfinf\infinf父亲节点v1v3v1v1-1v4-1-1-1第八步再取距离最小的节点 v2 作为中转点更新从 v2 可到达的节点标号注意比较与原距离的大小 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1111100000距离0531611inf\infinfinf\infinfinf\infinf父亲节点v1v3v1v1v2v4-1-1-1第九步再取距离最小的节点 v5 作为中转点更新从 v5 可到达的节点标号注意比较与原距离的大小 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1111110000距离0531611inf\infinfinf\infinfinf\infinf父亲节点v1v3v1v1v2v4-1-1-1第十步更新后的结果 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1111110000距离0531610912inf\infinf父亲节点v1v3v1v1v2v5v5v5-1第十一步再取距离最小的节点 v7 作为中转点更新从 v7 可到达的节点标号注意比较与原距离的大小 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1111110100距离0531610912inf\infinf父亲节点v1v3v1v1v2v5v5v5-1第十二步再取距离最小的节点 v6 作为中转点更新从 v6 可到达的节点标号注意比较与原距离的大小 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1111111100距离0531610912inf\infinf父亲节点v1v3v1v1v2v5v5v5-1第十三步再取距离最小的节点 v8 作为中转点更新从 v8 可到达的节点标号注意比较与原距离的大小 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1111111110距离053161091215父亲节点v1v3v1v1v2v5v5v5v8第十四步最终结果 节点v1v2v3v4v5v6v7v8v9是否已被访问0/1111111111距离053161091215父亲节点v1v3v1v1v2v5v5v5v8可以从终点v8倒推v8⇐v5⇐v2⇐v3⇐v1v_8 \Leftarrow v_5 \Leftarrow v_2 \Leftarrow v_3 \Leftarrow v_1v8⇐v5⇐v2⇐v3⇐v1这就是最短路径。将路径上的权值相加可以得出最短路径的长度为12可以直接有 v8 那一列的距离得出结果如图 若只考虑路径长度而不考虑具体路径还可以这样列表 v1v2v3v4v5v6v7v8v90∞\infty∞∞\infty∞∞\infty∞∞\infty∞∞\infty∞∞\infty∞∞\infty∞∞\infty∞$631∞\infty∞∞\infty∞∞\infty∞∞\infty∞∞\infty∞$63∞\infty∞11∞\infty∞∞\infty∞∞\infty∞$5∞\infty∞11∞\infty∞∞\infty∞∞\infty∞$611∞\infty∞∞\infty∞∞\infty∞$10912∞\infty∞$10912∞\infty∞$12∞\infty∞$15加粗的数字即为从起点到各节点的最短路径长度。 Dijkstra迪杰斯特拉算法的局限 DijkstraDijkstraDijkstra迪杰斯特拉算法可以用于解决无向带权图和有向带权图的最短路径问题。但是要求权重全是正数不能使负数。为了解决带负权重的最短路径问题我们可以采用 Bellman−FordBellman-FordBellman−Ford贝尔曼-福特算法来解决。
五、Bellman-Ford算法
贝尔曼-福特算法实际上处理的是具有负权重的有向图且该有向图不能含有负权回路因此函数负权回路的图可以在权重的回路中不断循环路径长无穷小 贝尔曼-福特算法简介 更新规则如果A与B的距离 A列表中的距离 B列表中的距离那么我们就将B列表中的距离更新为较小的距离并将B的父亲节点更新为A。 在 Matlab 中使用贝尔曼-福特算法 在 MatlabMatlabMatlab 中调用命令[P, d] shortestpath(G, start, end [, Method, algorithm]) 输入参数{G:输入图对象start:起始的节点end:目标的节点[,′Method′,algorithm]:可选参数表示计算路径所使用的算法。默认为‘auto’输入参数\left\{ \begin{aligned} G:\text{输入图对象} \\ start:\text{起始的节点} \\ end:\text{目标的节点} \\[, Method, algorithm]:\text{可选参数表示计算路径所使用的算法。默认为‘auto’} \end{aligned}\right.输入参数⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧G:输入图对象start:起始的节点end:目标的节点[,′Method′,algorithm]:可选参数表示计算路径所使用的算法。默认为‘auto’ 输出参数{P:最短路径经过的节点d:最短距离输出参数\left\{ \begin{aligned} P:\text{最短路径经过的节点} \\ d:\text{最短距离} \end{aligned} \right.输出参数{P:最短路径经过的节点d:最短距离 可选的算法{auto:自动选择算法unweighted:广度优先计算将所有便权重视为1positive:Dijkstra算法mixed:Bellman-Ford算法可选的算法\left\{ \begin{aligned} auto:\text{自动选择算法} \\ unweighted:\text{广度优先计算将所有便权重视为1} \\ positive:\text{Dijkstra算法} \\ mixed:\text{Bellman-Ford算法} \end{aligned}\right.可选的算法⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧auto:自动选择算法unweighted:广度优先计算将所有便权重视为1positive:Dijkstra算法mixed:Bellman-Ford算法
六、总结
根据图的类型确定算法 无向带权图、有向带正权图——Dijkstra算法有向带负权图不含负权回路——Bellman-Ford算法 根据具体的算法过程计算或者使用Matlab等工具计算。
如果有什么错误请一定提出哦~~~
