最短路径算法中Dijkstra算法的优化及应用(2)

1.2 最短路径算法的研究意义
最短路径算法是计算机科学与地理信息科学等领域研究的热点，在人们的日常生活中得到很多的应用。如：对于旅客来说，如果他要从甲地到乙地，他希望选择一条途中中转次数最少的路线，怎样节省交通费用，应该选择哪条路才能使自己的费用最低、时间最少。最短路径算法中传统的Dijkstra算法一般用于计算一个源节点到所有其他节点的最小代价路径，并且能够适应网络拓扑的变化，性能稳定，在运输路线规划等领域都应用广泛。因此，对最短路径问题的研究是很有必要的。
1.3 已有Dijkstra算法存在的问题
原始Dijkstra算法，在存储图形数据、运算时，需要根据其节点与距离之间的关系，形成关联矩阵、距离矩阵与邻接矩阵，需要定义的数组来存储数据，是网络的节点数，网络中的节点数较大时，会占用较大的计算机内存。
2.经典的Dijkstra算法
2.1 Dijkstra算法的思想
设集合存放已经求得最短路径的终点，则为尚未求得最短路径的终点集合。初始状态时，集合中只有一个源点，设为结点。迪杰斯特拉算法的具体做法是：首先将源点加入中；在算法的每一步中，按照最短路径值的非减次序，产生下一条最短路径( ~> ),并将该路径的终点加入中；直到 ,算法结束。
为实现迪杰斯特拉算法，设计下列数据结构。
(1)一文数组中存放从源点到结点的当前最短路径的长度。
(2)一文整型数组存放从源点到结点的当前最短路径上，结点的前一个结点。
(3)一文布尔数组，若为true，表示结点在中；否则，表示在中。
下面简述迪杰斯特拉算法计算过程。
(1)求第一条最短路径
在初始状态下，集合中只有一个源点，，所以
,
式中，是边的权值。所以对所有节点 , 有当前最短路径的长度。第一条最短路径是所有最短路径中的最短者，它必定只包含一条边 ,并满足

(2)更新和
    将结点加入中，并对所有的按上式修正，即

式中，是边上的权值。
(3)求下一条最短路径
在中,选择具有最短路径的当前最短路径值的结点 ,满足

2.2 Dijkstra算法的步骤
    Dijkstra算法的主要步骤如下：
(1)初始化：创建递减长度为的一文数组、和，并将每个初始化为false, 为，如果 != 且 , 则 , 否则。
(2)将源点加入集合中： =true；。
(3)使用for循环，按照长度的非递减次序，依次产生条最短路径，调用函数Choose,选出最小的；将结点加入集合中， =true；使用内层for语句更新数组和的值，使得其始终代表各条当前最短路径。
迪杰斯特拉算法
Template<class T>
class MGraph
{
public:
     MGraph(int mSize);
     void Dijkstra(int s,T*& d,int *& path);
     ...
private:
     int Choose(int* d,bool* s); //在一文数组d中求最小值
     T**a; //动态生成二文数组a，存储图的邻接矩阵

     int n;   //图中顶点数
}；
Template<class T>
Int MGraph<T>::Choose(int* d,bool* s)
{
     int i,minpos;T min;
min=INFTY;minpos= -1;
for(i=1; i<n; i++)
    if(d[i]<min && ! s[i]){
       Min=d[i]; minpos=i;
    }
return minpos;
}
Template<class T> 最短路径算法中Dijkstra算法的优化及应用(2):http://www.751com.cn/jisuanji/lunwen_4785.html