最短路径算法过程

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

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

1 道路网模型及权重设置

1.1 道路网模型建立

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

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

6.3.3 最短路径算法--Dijkstra算法，Bellmanford算法，Floyd算法，Johnson算法

最短路径算法

在交通地图上，两地点之间的路径通常标有长度，我们可以用加权有向来描述地图上的交通网。加权有向图中每条路径都有一个路径权值，大小为该路径上所有边的权值之和。本节将重点讨论顶点之间最短路径问题。在实际问题中，路径权值还可以表示其它类型的开销，例如两地之间行程所需要的时间；两任务切换所需代价等。

本节讨论的最短路径具有方向性，问题用图的术语描述为：给定一个起始顶点s和一个结束顶点t，在图中找出从s到t的一条最短路径。称s为路径源点，t为路径汇点。

最短路径问题可以进一步分为单源最短路径和全源最短路径。

单源最短路径定义为，给定起始顶点s，找出从s到图中其它各顶点的最短路径。求解单源最短路径的算法主要是Dijkstra算法和Bellman-Ford算法，其中Dijkstra算法主要解决所有边的权为非负的单源最短路径问题，而Bellman-Ford算法可以适用于更一般的问题，图中边的权值可以为负。

全源最短路径定义为，找出连接图中各对顶点的最短路径。求解全源最短路径的算法主要有Floyd算法和Johonson算法，其中Floyd算法可以检测图中的负环并可以解决不包括负环的图中的全源最短路径问题；Johonson算法同样也是解决不包含负环的图的全源最短路径问题，但是其算法效率更高。

1 基本原则

最短路径算法具有最短路径的最优子结构性质，也就是两顶点之间的最短路径包括路径上其它顶点的最短路径。具体描述为：对于给定的带权图G=(V, E)，设p=是从v1到vk的最短路径，那么对于任意i和j，1≤i≤j≤k，pij=为p中顶点vi到vj的子路径，那么pij是顶点vi到vj的最短路径。

最短路径算法都使用了松弛(relaxation)技术。开始进行一个最短路径算法时，只知道图中边和权值。随着处理逐渐得到各对顶点的最短路径的信息。算法会逐渐更新这些信息，每步都会检查是否可以找到一条路径比当前给定路径更短。这一过程通常称为“松弛”。

最短路径dijkstra算法流程

最短路径算法是计算在带权有向图或者无向图中起点到所有其他点最短路径的一种算法，其中最短路径指的是边权值之和最少的路径。目前最常用的算法是Dijkstra算法，它是由荷兰计算机科学家Edsger W. Dijkstra于1959年提出的。下面将介绍Dijkstra算法的流程。

1. 初始化

首先，需要将起点到每个点的最短距离都初始化为无穷大，除了起点自己的最短距离为0。其中，起点是指算法的起点节点。同时，需要创建一个集合S，用于记录已经确定了最短距离的点。

2. 找出未确定最短路径的节点中最小的距离，并将其标记为已确定最短路径

在第一步中，只有起点节点的最短距离是确定的。接下来，在集合S中找出剩余未确定最短路径的节点中距离最小的节点u，并将其标记为已经确定了最短路径。在第一次执行该步骤时，节点u即为起点节点。

3. 更新最短距离

将节点u所有邻居的距离进行更新。假设节点v是节点u的邻居，其距离为d(u,v)，则： 如果 d(u,v) + dist(u) < dist(v)，则更新节点v的最短距离为d(u,v) + dist(u)，其中dist(u)表示起点节点到节点u的最短距离。

重复执行上述步骤，直到集合S中包含所有节点。

4. 输出每个节点的最短距离

执行完第三步之后，每个节点的最短距离都已经确定。此时，可以输出每个节点的最短距离。

以上就是Dijkstra算法的流程。此外，这个算法还可以通过堆优化来提高效率。具体来说，可以将还未确定最短距离的节点按照距离从小到大存储在堆中，每次取出堆中距离最小的节点。（这部分由于是在原算法的基础之上的优化模型，所以该模型不友好于百科网站的格式要求，如果您有需要，也可以决定不包括，并以此作为描述结尾）

总的来说，Dijkstra算法是求解最短路径问题的有效方法之一。它适用于只有正权边的有向或者无向图，并且能够计算出起点到所有其他节点的最短路径。因此，它可以用于路线规划、制订地图等应用情景中。

文字描述用bfs算法求单源最短路径的过程

BFS（广度优先）算法用于求解单源最短路径问题，其基本过程如下：

1.创建一个队列，并将源点加入队列中。

2. 创建一个数组 dist[]，用于存储源点到各个顶点的最短路径长度。初始化 dist[] 数组，将所有顶点的最短路径长度设置为无穷大，将源点的最短路径长度设置为0。

3. 创建一个数组 visited[]，用于标记顶点是否已经被访问过。初始化 visited[] 数组，将所有顶点的标记设置为未访问。

4.开始循环直到队列为空：

a.从队头取出一个顶点v，标记顶点v为已访问。

b.遍历顶点v的邻接顶点：

i. 如果邻接顶点 u 尚未被访问过，则将顶点 u 加入队列中，并更新顶点 u 的最短路径长度为 dist[v] + 1

c.检查队列中是否还有未访问的顶点，如果有则回到步骤4a。

5. 循环结束后，dist[] 数组中存储的即为源点到各个顶点的最短路径长度。

6. 如果需要求解最短路径的具体路径，可以使用一个数组 prev[]

来记录每个顶点的前驱顶点，即 prev[u] 表示顶点 u 在最短路径上的前驱顶点。通过 prev[] 数组可以回溯出最短路径。

以上步骤即为使用BFS算法求解单源最短路径的过程。