最短路径路由算法

随着计算机和地理信息科学的发展,地理信息系统因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一,在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用,通用的网络分析功能包括路径分析、资源分配、连通分析、流分析等。网络分析中最基本和最关键的问题是最短路径问题,它作为许多领域中选择最优问题的基础,在交通网络分析系统中占有重要地位。

从道路网络模型的角度看,最短路径分析就是在指定道路网络的两节点间找出一条阻碍强度最小的路径。根据阻碍强度的不同定义,最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。相应地,最短路径问题就成为最快路径问题、最低费用问题等。因此,城市道路网作为一种大型网络设施有其本身的特征。它一方面包含网络本身的拓扑特征;另一方面还包含了大量反应地理位置特征的几何数据。本文根据道路网的特点,运用GIS网络分析功能对道路网络模型、道路的权重选择以及快速寻求路网中两节点间的最短路径算法分别进行了研究。

1 道路网模型及权重设置

1.1 道路网模型建立

城市道路网主要由众多道路相交、相连构成。在纵横交织、错综复杂的道路网络中,道路间的地理位置关系相当复杂,一条道路可能与若干条道路相交相连,且其相交相连的模式复杂。为了避免过多地考虑道路间的拓扑关系,抽取道路网中道路交叉路口作为分析对象,并对道路以交叉路口为结点进行分割,成为路段。这样,整个网络图将由交叉路口点和路段组成,并定义交叉路口点为网络的结点,路段为网络的弧。从而建立基于路段连接的网络模型,其模型形式表述为:

式中,RW代表道路网络;N代表结点集;R代表路段集合,其元素为有序对,表示由结点x到结点y存在一条有向通路;LR代表路段长度集合,其元素表示有向路段的加权长度。其中,路段的加权长度是指根据目标函数要求,综合各种动态实时信息和静态属性信息后所得的路段参数,而并非真实意义下的长度。

最短路径路由算法

一、案例图形分析

为了分析最短路径路由，模拟构造的一个图，如下所示：

二、相关理论：

Dijskstra算法：用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijskstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

例如：

1、要求出（1110－1116）的最短路径

第一步：以开始点1110分别路由（1110－1114）、（1110－1115）、（1110－1112）得出 （1110－1114）为：30

（1110－1115）为：100

（1110－1112）为：10

通过比较得出（1110－1112）的距离最短。

第二步：以点1112为基础开始路由（1112－1113），（1112－1110）[备注：因为1110已经被路由过，所以不在选择这条路路由]，（1112－1116），（1112－1111）得出

（1110－1112－1113）为：17

（1110－1112－1116）为：30

（1110－1112－1111）为：15

通过比较得出（1110－1112－1111）这条路最短。

第三步：以点1111为基础开始路由（1111－1112）[备注：因为1112已经被路由过，所以不在选择这条路路由]，（1111－1116）得出

（1110－1112－1111－1116）为：24

通过以下比较：

（1110－1114）为：30

（1110－1115）为：100

（1110－1112－1113）为：17

（1110－1112－1116）为：30

（1110－1112－1111－1116）为：24

得出（1110－1112－1113）这条路最短

第四步：以点1113为基础开始路由（1113－1114）、（1113－1115）、(1113－1112)[备注：因为1112已经被路由过，所以不在选择这条路路由]得出

贝尔曼福德算法

简介

贝尔曼福德算法（Bellman-Ford Algorithm）是一种用于解决单源最短路径问题的算法。它可以处理带有负权边的图，并且能够检测负权回路。贝尔曼福德算法的时间复杂度为O(V * E)，其中V表示图中顶点的数量，E表示图中边的数量。

贝尔曼福德算法是由理查德·贝尔曼（Richard Bellman）和莱斯特·福特（Leslie Ford）于1958年提出的。它是一种动态规划算法，通过逐步迭代来逐渐确定从源点到其他顶点的最短路径。

算法原理

贝尔曼福德算法通过不断更新顶点的最短路径估计值来逐渐逼近最短路径。算法的基本思想是，假设图中最长的路径长度不超过D，那么对于任意两个顶点u和v，从u到v的最短路径最多包含D-1条边。

算法的具体步骤如下：

1. 初始化：将源点s的最短路径估计值dist[s]设置为0，其他顶点的最短路径估计值dist[v]设置为正无穷大（表示不可达）。

2. 迭代更新：对于图中的每条边(u, v)，如果dist[u] + weight(u, v) <

dist[v]，则更新dist[v]为更小的值dist[u] + weight(u, v)。

3. 检测负权回路：重复上述步骤|V|-1次后，再进行一次迭代。如果在这次迭代中，仍然存在dist[u] + weight(u, v) < dist[v]的边，则说明图中存在负权回路。

4. 输出结果：如果不存在负权回路，则dist数组中存储的就是从源点s到其他顶点的最短路径长度。

算法实现

下面是贝尔曼福德算法的伪代码实现：

function BellmanFord(Graph graph, Vertex source):

// 初始化

for each vertex v in graph:

dist[v] := infinity

dist[source] := 0

Dijkstra算法是一种用于计算图中从一个顶点到其他所有顶点的最短路径的算法。它由荷兰计算机科学家艾兹赫尔·戴克斯特拉于1956年提出。Dijkstra算法的基本思想是通过不断更新起始顶点到其他顶点的最短路径长度，逐步找到最短路径。以下将详细介绍Dijkstra算法的步骤，并给出一个例题和表格供读者参考。

一、算法步骤

1. 初始化

- 设置起始顶点的最短路径为0，其余顶点的最短路径为无穷大。

- 将起始顶点加入已访问的顶点集合。

2. 更新

- 从未访问的顶点中选择离起始顶点最近的顶点，将其加入已访问的顶点集合。

- 更新起始顶点到其他顶点的最短路径长度，如果经过新加入的顶点到其他顶点的路径长度小于当前已知的最短路径长度，则更新最短路径长度。

3. 重复更新直到所有顶点都被访问过。

二、算法实例

为了更好地理解Dijkstra算法的具体应用步骤，我们通过一个实际的例题来演示算法的执行过程。

假设有以下带权重的图，起始顶点为A：

顶点 A B C D E

A 0 3 4 ∞ ∞

B ∞ 0 ∞ 1 7

C ∞ 4 0 2 ∞

D ∞ ∞ ∞ 0 5

E ∞ ∞ ∞ ∞ 0

表中每个元素表示从对应顶点到其它顶点的边的权重，"∞"表示没有直接相连的边。

我们按照Dijkstra算法的步骤来计算从顶点A到其他顶点的最短路径长度。

1. 初始化

起始顶点为A，初始化A到各顶点的最短路径长度为0，其余顶点的最短路径长度为∞。将A加入已访问的顶点集合。

2. 更新

选择A到B的路径长度最短，将B加入已访问的顶点集合。更新A到C和A到D的最短路径长度。

3. 重复更新

依次选择离起始顶点最近的顶点，并更新最短路径长度，直到所有顶点被访问。

通过不断的更新，最终得到从顶点A到其他顶点的最短路径长度表格如下：