最短路径算法

　　[摘要]最短路径问题是图论中的一个重要问题，其应用面相当广泛。到目前为止，最短路径算法及其应用已成为一个专业课题。本文将从其源自的数学分支——图论开始引入，重点介绍最短路径的两个重要算法和最短路径算法在交通道路方面的应用。
　　[关键词]最短路径，图论，算法，
　　
　　1.引言
　　最短路径问题是图论研究中的一个重要问题，因此它的研究成为不同领域专家学者共同关注的问题。提出许多行之有效的算法。对于各种实际问题的解决提供了数学依据。随着研究的深入，最短路径算法也越来越丰富。本文将对最短路径问题从逻辑联系上做一下串接，对两个重要的算法进行系统的介绍。
　　2.最短路径问题
　　图论是一种直观、清晰地表达已知信息的方式。特别是随着计算机科学的发展，图论也得到迅速的发展，成为一个十分活跃的数学分支。特别是图论中的最短路径问题被广泛的应用在工程、运输等方面，尤其在运筹学模型中最短路径问题已是不可缺少的一种方法。
　　我们可以用顶点代表城市，两个顶点之间的连线代表在两个城市之间建造的铁路。整个铁路系统构成一个连通图，任意两个顶点之间都有一条通路。在连通图中联系两个顶点的边上标注一个数值，代表这两个顶点（城市）的实际距离或铁路造价。这样就将一个实际问题转化成了一个最短路径问题。
　　像这样的每条边上都标注了一个数值的图，我们称之为带权图。一般地设，若相对的每条边都有一个实数，则称为边上的权，并称为带权图。当时（e是连接两个顶点，的边），也可将记作，并规定任意的，，当，不相邻时，。
　　在一个带权连通图中，、为任意两点，从到可能有好几条路径，在这些路径中，从到的带权总和最小的那条路径，即为从到的最短路径。的带权总和便为从到的距离，记作。
　　最短路径问题一般包括以下五种情况：1．从某一节点到其它所有节点之间的最短路径；2．在各对节点之间的最短路径；3．在两个规定节点之间的最短路径；4．从某些规定节点通过某些规定节点之间的最短路径；5．次短或较短路径等。
　　第一种情况应用得最为广泛。要寻找某一节点到其他所有节点之间的最短路径，实质上是要生成一棵路径树。如图1所示，它正是节点1到其余所有节点的一棵路径树，其中树根即为节点1。某节点V的后继节点是指从到树根（r）唯一路径上的相邻节点。例如，节点2的后继节点为节点1，节点7的后继节点为节点3。显然树根没有后
　　继节点。
　　
　　图1路径树
　　这样，此路径树则可由一系列后继节点来确定。图1所示的树可由—，1，1，3，4，3，3来定义。它实际上可看成是一个数组，其中第项可用表示，它标示出网络中第个节点的后继节点号。如该数组中符号“—”表示节点1（树根）没有后继节点，第2项“1”表示节点2的后继节点是1号节点，如此等等。另外，从某节点到根节点（）的唯一路径也能通过一系列后继节点来跟踪。如图1中节点7到根节点1的路径可从节点7到（节点3），然后到（节点1）。该数组为。最短路径算法的基本设计思想正是基于上述原理，即从所有其它节点到节点的路径将形成一棵树；树中从某个节点到根节点的唯一路径即为节点和之间的最短路径。
　　3.最短路径问题两个重要算法
　　最短路径问题是一种“最优解”问题，其算法多种多样。其中著名的有Dijkstra算法和Ford-Fulkerson算法。此外还有蚂蚁算法、Warshall算法、动态规划算法。这些算法本文本文不做具体介绍。
　　(1)Dijkstra算法
　　求最短路径的较好算法是由丹麦计算机科学家B.W.Dijkstra于1959年给出的标号法，也称Dijkstra算法。算法解决的是有向图中最短路径问题。举例来说，如果图中顶点表示城市，而边上的权表示城市间的距离。Dijkstra算法可以用来找到两个城市之间的最短路径。而且它可为任一源顶点找出与其它所有节点的最短路径。在寻径时要分步由源节点开始一步步地向相邻顶点扩展，直到包含所有网络节点为止。
　　其方法是：建立一个节点集，开始时只包含源节点，每算一步中增加一个相邻节点，直到所有网络节点均进入中后才结束计算。算法步骤如下：
　　1．初始化处理，定义数组，它只包含源节点，，并定义距离，为非源节点中的其它某个节点，该距离为节点到源节点的链路长度；若与直接相邻，则有一确定值。若与不直接相邻，则。
　　2．不断求得数组以外的节点，使距离最小，并将节点F加入原来的数组，对于以外的各节点，按下式更新距离：
　　
　　当，则以代入原，否则维持原值不变。这一过程重复至所有节点均包含在数组N为止。
　　该算法的实现流程主要包括：输入节点邻接矩阵，输入源节点号，输入距离，计算最短距离；修改源节点号，重新输入距离，重新计算最短距离，重复此过程，直至所有节点均被修改为源节点号为止。
　　Dijkstra算法的主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法还有一个缺点，那就是它对应的图，如果图是全连通的，那么这种算法肯定是很好的，如果不是全连通的，最终的值就不一定是最优的。
　　(2)Ford-Fulkerson算法
　　Ford-Fulkerson算法是另一种著名的最短路经算法。这一方法是用一对数给每一个节点进行标志，并逐步修改，最后得到最短路径。在此算法中，若由某节点向另一节点发送报文，先要发送给它的相邻节点，若是的相邻节点集，而是其中的一个节点，则必有：，式中为节点经到的通路长度；为，两相邻节点间的距离；为由到的最短路径长度。
　　若中考虑了每一个节点，并对每一个相邻节点均按上式计算一遍，然后比较结果，找出其中最短的一个，记为，它即为最短路径
　　
　　同理可得到到的最短路径。这样一直进行到目的节点A。该算法的具体步骤如下：
　　1．初始化处理，对所有节点都给予形式的标号。
　　2．求每个节点与源节点的最短距离，并反复修改节点上的标号为最短距离的标号，寻找支路，使之满足

 1/2    1 2 下一页 尾页