最短路径的Dijkstra算法.PDF

The Dijkstra Algorithm 最短路径的Dijkstra 算法 The Dijkstra Algorithm eryar@163.com 摘要 本文用C 实现了图的最短路径Dijkstra 算法，并将自己理解该算法的方式与大家 分享下，若有错误之处，欢迎指正。 关键字：图、最短路径、Graph、Dijkstra 一、引言 Introduction 对图G 中的每一条边e 都赋以一个实数w(e) ，则G 连同它边上的权称为赋权图。赋权 图经常出现在图论的实际应用问题中，边上的权（Weight ）可以表示各种实际意义，如在输 送网络中，权可以表示两地的距离，可以表示运输的时间，还可以表示运输的费用 。许多 最优化问题相当于在一个赋权图中找出某类具有最小 （或最大）权的子图。例如，给出一个 连接各城镇的铁路网，要找出一条给定两个城镇间的最短路线。这个问题的图论模型建立如 下：以顶点代表城镇，边代表城镇间的铁路线，权表示直接相连的城镇之间的铁路距离，得 到一个赋权图，即网络N 。 本文讨论带权的有向图，并称路径上的第一个顶点为源点 （Source ），最后一个顶点为 终点 （Destination ）。 二、算法理解 Understanding the Algorithm Dijkstra 算法描述为 假设用带权邻接矩阵来表示带权有向图。首先引进一个辅助向量 D ，它的每个分量D [i]表示当前所找到的从始点v 到每个终点Vi 的最短路径。它的初始状态 为：若两顶点之间有弧，则D [i]为弧上的权值；否则置D [i]为无穷大。 u 找到与源点v 最近的顶点，并将该顶点并入最终集合S ； u 根据找到的最近的顶点更新从源点v 出发到集合V-S 上可达顶点的最短路径； u 重复以上操作。 eryar@163.com 2013-1-1 The Dijkstra Algorithm 图1 带权有向图 以前总是认为Dijkstra 算法可以用来求从源点到指定终点的最短路径，导致总不能抓住 算法的中 思想。现在认为把握Dijkstra 的算法要点为 u Dijkstra 提出了一个按路径长度递增的次序产生最短路径的算法； u 每次循环都可以得到一个从源点到某个顶点的最短路径，某个即不是确定的一个； 以带权有向图1 为例说明Dijkstra 算法的执行过程 假设源点为v0，则初始状态时源点到其 它各顶点的距离为 源点 终点 v1 v2 v3 v4 v5 v0 ∽ 10 ∽ 30 100 由上表可知，与源点v0 最近的顶点为v2，距离为10 。 将v2 加入到最终顶点集合S 中。 再根据v2 更新从源点到其它顶点的最短距离，即从v0-v2-v3 的距离为60 ∽，所以将v0 到 v3 的距离更新为60，如下表所示 源点 终点 v1 v2 v3 v4 v5 v0 ∽ 10 60 30 100 由上表可知，与源点v0 次近的顶点为v4，距离为30 。 将v4 加入到最终顶点集合S 中； 再根据v4 更新从源点到其它顶点的最短距离。即从v0-v4-v3 的距离为5060，所以将v0 到 v3 的距离更新为50 ；从v0-v4-v5 的距离为90100，所以将v0 到v5 的距离更新为90。 源点 终点 v1 v2 v3 v4 v5 v0 ∽