1、 数据结构课程数据结构课程论文论文 设计题目：Dijkstra 算法和排序器（排序算法验证及评价） 1 图的图的 Dijkstra 算法算法 一、一、课题内容和要求课题内容和要求 Dijkstra 算法的实现和演示。 二、设计思路分析 Dijkstra 算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中 dj 是从起源点 s 到点 j 的最短路径的长度 (从顶点到其本身的最短路径是零路(没 有弧的路)，其长度等于零)；pj则是从 s 到 j 的最短路径中 j 点的前一点。求解 从起源点 s 到点 j 的最短路径算法的基本过程如下： 1) 初始化。起源点设置为： ds=0, ps为
2、空; 所有其他点: di=, pi=?; 标记起源点 s，记 k=s,其他所有点设为未标记的。 2) 检验从所有已标记的点 k 到其直接连接的未标记的点 j 的距离，并设置： dj=mindj, dk+lkj 式中，lkj是从点 k 到 j 的直接连接距离。 3) 选取下一个点。从所有未标记的结点中，选取 dj 中最小的一个 i： di=mindj, 所有未标记的点 j 点 i 就被选为最短路径中的一点，并设为已标记的。 4) 找到点 i 的前一点。从已标记的点中找到直接连接到点 i 的点 j *，作为 前一点,设置： i=j * 5) 标记点 i。如果所有点已标记，则算法完全推出，否则，记
3、k=i，转到 2) 再继续。 2 三、概要设计三、概要设计 算法流程图如下图所示： CGraph类的声明部分如下所示： #define maxPoint 100 class CGraph public: CGraph(void); CGraph(void); bool SetGraph( double gmaxPointmaxPoint , int startPoint , int size ); 将节点放入优先队列 从优先队列中取出当前最优元素并算出当 前这个可行解的路径长度和耗费并与最优 解比较 不如下界？ 选择头节点 Y 将这个节点保存下来作为剪枝使用的下界 队列为空? Y 分 析 当
4、前 的 下 界,得出 程 序结 果,并返回. N 利用 Dijkstra 算法算出各节点到目 标节点的最短距离 N 3 bool Dijkstra(); void Display(); int GetStartPoint(); bool setStart(int start); void ChangeMatix(double (*p)maxPoint); double GetBestWay( int dest , int path , int private: bool solved;/标志当前图是否已经求解 double graphmaxPointmaxPoint;/当前图布局 int size;/地图大小 int startPoint;/起点 double distmaxPoint;/当前图的解 int prevmaxPoint; ; 四、详细设计四、详细设计 / Dijkstra2.cpp : Defines the entry point for the c
