最短路径算法中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>