最短路径法的说明与实施
最短路径问题是图论研究中的一个经典算法问题，旨在寻图（由结点和路径组成的）中两结点之间的最短路径。如何用matlab将已知点连线最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其它的度量，如时间、费用、线路容量等等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。对于单源点的最短路径问题，一般采用经典的最短路径算法——Dijkstra算法，只是不同系统对Dijkstra算法采用了不同的实现方法。但是Dijkstra算法比较繁琐，所以在进行计算的时候我们可以把它转化为Floyd算法。然后再编程实现了该算法[23]。
  Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率较低，但作为解决一般最短路问题的方法还是值得我们学习的。
最短路径算法的思路介绍
Dijkstra 算法思想为：设G=（V，E）是一个带权有向图（也可以是无向图，无向图是有向
图的特例）， 把图中顶点集合V分成两组：第一组为已求出最短路径的顶点集合（用S 表示，初始时S 中只有一个源点，以后每求得一条最短路径，就将其加入到集合S 中，直到全部顶点都加入到S 中，算法就结束了）；第二组为其余未确定最短路径的顶点集合（ 用U 表示）， 按最短路径长度的递增次序依次把第二组的顶点加入S 中。在加入的过程中，总保持从源点v 到S 中各顶点的最短路径长度不大于从源点v 到U 中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S 中的顶点的距离就是从v 到此顶点的最短路径长度，U中的顶点的距离，是从v 到此顶点只包括S 中的顶点为中间顶点的当前最短路径长度。其步骤主要有[11]：
第一，初始时，S 只包含源点，即S＝{顶点}，v 的距离为0。U 包含除v 外的其他顶点，U 中顶点u 距离为边上的权（若v 与u 有边）或（若u 不是v 的出边邻接点）。
第二，从U 中选取一个距离v 最小的顶点k，把k 加入S 中（该选定的距离就是v 到k 的最短路径长度）。
第三，以k 为新考虑的中间点，修改U 中各顶点的距离； 若从源点v 到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u 的距离值，修改后的距离值的顶点k
的距离加上边上的权。
第四，重复步骤第二步和第三步直到所有顶点都包含在S 中。
3.1.2 最短路径算法的实施步骤
假如某企业要将一批产品由A 地运往F地，从A到F有多条路线选择，怎样选择可以使运输线路最短，当然在实际问题中权可以认为是费用，效率等因素。用Dijkstra 算法可以这样进行，在A、F 两地的交通图中的点B、C、D、E 分别表示四个地名，点与点之间的连线表示两地之间的公路，边上所赋值代表两地间的长度（单位为公里）如图3.1所示：
5
3
                    图3.1  A到F点的交通模型图
第一，在S 集合中：进入A，此时S=<A>，此时最短路径为A→A=0，以A 为中间点， 从A 开始。在U 集合中：U=<B，C，D，E，F>，A→B=6，A→C=3，A→其他U 中的顶点=∞，发现A→C=3 权值为最短。
第二，在S 集合中：进入C，此时S=<A，C>，此时最短路径A→A=0，A→C=3，以C 为中间点，从A→C=3 这条最短路径开始。在U 集合中：U=<B，D，E，F>，A→C→B=5（比A→B=6 要短），此时到B权值为A→C→B=5，A→C→D=6，A→C→E=7，A→C→其他U 中的顶点=∞，发现A→C→B=5 权值为最短。
第三，在S 集合中：进入B，此时S=<A，C，B>，此时最短路径A→A=0，A→C=3，A→C→B=5， 以B 为中间点， 从A→C→B=5 这条最短路径开始。在U 集合中：U=<D，E，F>，A→C→B→D=10（比第二步的A→C→D=6 要长），此时到D权值改为A→C→D=6，A→C→B→其他U中的顶点=∞， 发现A→C→D=6 权值为最短。
第四，在S 集合中：进入D，此时S=<A，C，B，D>，此时最短路径A→A=0，A→C=3，A
→C→B=5，A→C→D=6，以D 为中间点，从A→C→D=6 这条最短路径开始。在U 集合中，U=<E，F>，A→C→D→E=8 （ 比第二步的A→C→E=7 要长），此时到E权值更改为A→C→E=7，A→C→D→F=9，发现A→C→E=7 权值为最短。
第五，在S 集合中：进入E，此时S=<A，C，B，D，E>，此时最短路径为A→A=0，A→C=3，A→C→B=5，A→C→D=6，A→C→E=7，以E 为中间点，从A→C→E=7 这条最短路径开始。在U 集合中：U=<F>，A→C→E→F=12 （比第四步的A→C→D→F=9 要长），此时到F 权值更改为A→C→D→F=9，发现A→C→D→F=9 权值为最短。
第六，在S 集合中：进入F，此时S=<A，C，B，D，E，F>， 此时最短路径为A→A=0，
第七，得到最短路径。从第六步可知，从A 到F 的最短路径为9 公里，A 到B的最短路径为A→C→B=5，A 到C 是最短路径为A→C=3，A 到D 的最短路径为A→C→D=6，A 到E 的最短路径为A→C→E=7，所以A 到F 的最短路径为A→C→D→F=9。
Dijkstra算法提供了从网络图中某一点到其他点的最短距离。但实际问题中往往要求网络中任意两点之间的最短路距离。如果仍然采用Dijkstra算法对各点分别计算，就显得很麻烦。
所以就可以使用网络各点之间的矩阵计算法，即Floyd算法。Floyd算法的基本是：从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，在检查d(i,j)与d(i,k)+d(k,j)的值；在此d(i,k)与d(k,j)分别是目前为止所知道的i到k与k到j的最短距离。因此d(i,k)+d(k,j)就是i到j经过k的最短距离。所以，若有d(i,j)>d(i,k)+d(k,j)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(i,j)重写为d(i,k)+d(k,j)，每当一个k查完了，d(i,j)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(i,j)里面存放的就是i到j之间的最短距离了[7]。对于上面的问题，只要能列出它的距离的邻接矩阵，如表3.1所示。便能用floyd法进行计算了。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。