最短路径算法中Dijkstra算法的优化及应用(2)
时间:2017-04-11 13:20 来源:毕业论文 作者:毕业论文 点击:次
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> (责任编辑：qin) |