最短路径的研究

-精选财经经济类资料- -最新财经经济资料-感谢阅读- 1 最短路径的研究 【摘 要】经过实践证明，采用 自定义结构数组的方式来表示邻接表的 方法，其占用空间较小，花费时间较少， 编程难度较小，执行效率较高，在 Dijkstra 最短路径算法中是较优的一种 实现方法。 中国论文网 /5/view-5334145.htm 【关键词】最短路径；Dijkstra 1、最短路径的概念 最短路径指的是网络中两个点之 间的距离最小的计算路径。距离可以是 实际路程的距离，也可以是时间、流量 和运费等度量。 2、最短路径的 Dijkstra 算法原理 常用的最短路径算法有：Ford 算 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 2 法、Dijkstra 算法、Floyd 算法、Moore 算法、K 值算法等。本文主要就 Dijkstra 算法进行研究。Dijkstra 算法其 实是一种典型算法，它采取分步计算的 方法实现最短路径的计算。由一个起源 点到其他所有顶点的最短距离。主要特 征是由一个起始点不断地向外扩展，到 第一个点，再到第二个点，直至终点为 止。求解出来是起始点到所有其他各个 点的最短路径，并按照从小到大进行排 列。由于 Dijkstra 算法需要计算起始点 经过各个节点的距离，所以花费的时间 较长，相对效率较低，但是最后得到的 是最短路径的最优解。 3、Dijkstra 算法步骤 在有向图 G=（V，E）中，有 e 条弧和 n 个顶点，其中弧的集合为 E， 顶点的集合为 V，计算起源点 VS 至终 点 VT 之间最短路径。第一步骤：令邻 接矩阵 L（带权值）来代表有向图，其 中弧（X，Y）的权值用 L（X，Y）来 表示，用 L（X，Y）= 来假设当弧 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 3 （X，Y）不存在的情况；起源点 VS 与 顶点 X 之间的距离用 D（X）来表示， 很显然，起源点 VS 的 D 值为零，其余 各顶点为；已找到的起源点 VS 到顶 点之间最短距离的集合用 S 来表示，其 初始时为空集；没有找到的到顶点的最 短路径的集合用 V-S 来表示。第二步骤： 把起源点 VS 做好标记，设定 Y=VS，S= SVS ；第三步骤：在没 有找到到顶点的最短路径的集合中，当 D（Y）+ L（ Y，X） D（X）时，那 么令 D（Y）+ L（Y，X）= D（X） ，Y 为已做标记的节点；第四步骤：选取一 个顶点 Vk，使得 D（k） = min D（k） | Vk V-S ，当 D（k）= ， 那么表示起源点 VS 与 V-S 各顶点之间 没有路径，算法自动终止；相反，从起 源点 VS 开始到达所示终点的一条最短 路径就是 Vk，要对 Vk 做好标记。然后， 令 Vk=Y，并把其合并到集合 S，也就 是 S = S Vk；第五步骤：当终点 VT 和 Y 等值时，这代表这起源点 VS -精选财经经济类资料- -最新财经经济资料-感谢阅读- 4 至终点 VT 之间最短路径找到了，算法 自动终止，否则，将自动转到第三步骤 进行计算。 4、Dijkstra 算法分析 Dijkstra 算法中，网络的拓扑关 系一般是采用二维数组来存储，顶点之 间的关系在数组中可以清楚的表示出来， 这种实现方式就是邻接矩阵，这样二维 数组的存储空间为 n2，假设其中可用的 信息为 e 的话，那么 1-e/n2 就是它的冗 余度，要查找某个顶点的邻接点就要把 其他所有顶点都一起找过，也就是说查 找所有顶点的邻接点需要的时间为 T（n2） 。所以以邻接矩阵为实现方式的 缺点是占用空间大，执行效率低，优点 是编程简单，实现难度较小。Dijkstra 算法中，网络的拓扑关系一般是采用邻 接表来存储，相应顶点的链表或数组就 只存储其对应的顶点的相关数据，这种 实现方式就是邻接表，一般分为两种方 式：链表和结构数组。当链表所存储空 间为 e，因为其存储的数据都是有用信 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 5 息，所以冗余度为零，要查找某个顶点 的邻接点的次数就会减少，变成是其自 身的出度，查找所有顶点的邻接点需要 的时间为 T（e ） 。所以以链表为邻接表 实现方式的缺点是需要对各个顶点进行 指针设置，并相应地建立检查列，编程 相对难度较大，优点是占用空间小，执 行效率较高。在采用邻接表的实现方式 中，可以用结构数组来代替链表，这种 结构数组是自定义的。其计算原理：先 进行每个顶点的出度计算，可以得到其 最大值 Dmax；全部顶点的出度平均值 为 e/n；把当前的顶点的序号和出度存 储在邻接表中，当某个顶点的出度 Dmax 时，则赋值多余部分为-1；查找 某个顶点的邻接点花费的时间为 T（e+n） ，而每个顶点所用的时间为 T（n） ，在实际中，D 远小于 n；数组 占用存储空间为 （Dmax+1）*2n，其 中 2n*（D+1）为有用信息，计算其冗 余度为（Dmax-D ）除以（Dmax+1 ） ； 所以采用结构数组为方式的邻接表实现 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 6 方式特点是占用空间较小，执行效率较 高，花费时间较少，编程实现的难度较 小，是 Dijkstra 算法中较好的一种实现 方式。 5、Dijkstra 算法实例研究 在最短路径的实际应用中，我们 要进行计算的起点和终点大多数不是已 知的顶点。例如：我们要从某个地方 T 去 C 城市，而 T 位于 A、B 两个城市之 间，已知 T 跟 A 城市之间的距离为 200 公里，T 跟 B 城市之间的距离为 400 公 里，求地方 T 到 C 城市的最短路径。我 们的思路：分别计算出 AC 和 BC 的距 离，再把 AC 的距离+200 跟 BC 的距离 +400 进行比较，然后选择其中路径最 短的方案。由于起点和终点都是未知的 顶点，是处于已知两顶点之间的某一点， 按照以结构数组为实现方式 Dijkstra 算 法的话，要计算 4 次。在有向图 G =（V， E）中，有 e 条弧和 n 个顶点， 令起源点 VS 位于顶点 A 和 B 之间的弧 上，终点 Vt 位于顶点 C 和 D 之间的弧 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 7 上。把起源点 VS 与终点 Vt 放入邻接表 的网络中，那么弧的数量为 e+2，顶点 的数量为 n+2；在数组后面增加和 两个元素，其中代表起源点 VS，序 号为 1+n，出度为 2，NextNode1 设置 为 A， NextDist1 表示 VS 到顶点 A 的 距离，NextNode2 设置为 B， NextDist2 为 VS 到顶点 B 的距离，其 余全部赋值为-1；代表起源点 Vt，序 号为 2+n，出度为 2，NextNode1 设置 为 C， NextDist1 表示 Vt 到顶点 C 的 距离，NextNode2 设置为 D， NextDist2 为 Vt 到顶点 D 的距离，其余