GPS应用论文 第13页
最优路径搜索
3.1 最优路径选择模型的目标函数及约束条件
一般情况下，从起始点到终止点，往往有很多路径可以选择，那么选择一条最短的路径，将是这个系统最重要的一部分，也是最终目标。
3.2 最短路径搜索
在经典的最短路径算法之中，迪杰斯特拉（Dijkstra）算法是最适合用来进行道路网络中最短路径搜索的，所以，在现有的电子地图开发中，该算法被广泛运用。其基本思路是由近及远的寻找起点到其他所有节点的最短路径，当刚好找到所求终点的最短路径的时候，算法终止。
3.2.1 迪杰斯特拉（Dijkstra）算法基本思想
迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法，其本质是一个贪心算法。基本思想描述如下：
把网中所有顶点分成两组，第一组是已求出最短路径的顶点集合S，S集合的初值是源点（设为V1）;第二组是尚未确定最短路径的顶点集合T（即V - S）,T集合的的初值是除源点之外网中的所有顶点。按路径长度递增的顺序逐个把T集合中的顶点加到S集合中去，直至从源点V1出发可以到达的所有顶点都在S集合中。在这个过程中，总保持从V1到S集合各顶点的最短路径长度不大于从V1到T集合的任何顶点的最短路径长度。另外，每个顶点对应一个距离，S集合中顶点的距离是从V1到此顶点的最短路径长度，T集合中顶点的距离是V1到此顶点的只包括以S中顶点为中间顶点的当前最短路径长度。
3.2.2 迪杰斯特拉（Dijkstra）算法的具体实现
迪杰斯特拉（Dijkstra）算法具体的实现方法如下：
1、 假设用带权的邻接矩阵 cost 来表示有n个顶点的带权有向图。 cost [ i ] [ j ]表示弧< Vi，Vj >上的权值。若< Vi，Vj >不存在，则置cost[ i ] [ j ]为 ∞（可设表示无穷大的值为INT_MAX）。S为已找到从源点V出发的最短路径的终点的集合，它的初始值为V。那么，从V出发到图中其余各顶点（终点）Vi可能达到的最短路径的长度的初值为Dist[ i ] =cost [ V ][ i ]。
2、从T集合中选择w，使得Dist[ w ]=MIN{Dist[ i ] | Vi ∈V - S}，w就是当前求得的一条从V出发的最短路径的终点。从T集合中删除w，并入S集合，令S＝S∪{w}。
3、 修改从V出发到T集合中各顶点的最短路径长度。如果Dist[ w ]+cost[ w ][ i ]< Dist[ i ],则修改Dist[ i ]使Dist[ i ] = Dist [ w ]+cost [ w ][ i ]。
4、重复步骤2、3共 n - 1 次。数组 Dist 记录了从源点到图中其余各顶点的最短路径。
迪杰斯特拉（Dijkstra）算法用VC语言描述如下：
For i = 0 To n
dist(i) = g(k, i)
If dist(i) < 10000 Then
pre(i) = k
Else
pre(i) = -1
End If
Next
pre(k) = -1
dist(k) = 0
g(k, k) = 1
For j = 0 To n - 1
wm = 10000
p = -1
For i = 0 To n
If g(i, i) = 0 And dist(i) < wm Then
p = i
wm = dist(i)
751com.cn
Else
g(p, p) = 1
For i = 0 To n
If g(i, i) = 0 Then
If (dist(p) + g(p, i)) < dist(i) Then
dist(i) = dist(p) + g(p, i)
pre(i) = p
End If
End If
Next
End If
Next
用迪杰斯特拉算法求从起点到终点的最短路径，算法终止于终点离开T集合，加入到S集合时。
<< 上一页 [11] [12] [13] [14] [15] [16] [17] [18] 下一页
GPS应用论文 第13页下载如图片无法显示或论文不完整，请联系qq752018766
