刘敏

摘要：对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径的Dijkstra算法。对所设计的图的数据结构，提供必要的基本功能。建立图的表示模块，顶点的插入和删除操作模块；在建立图之后从单源点开始求最短路径并显示。实现的功能有建立有向图，排除和增加目的地，方便找出最短路径，在建立好的有向图中，显示出来从顶点到各个顶点的最短路径。

关键词：最短路径；有向图；数据结构

中图分类号：TP313文献标识码：A文章编号：1009-3044(2012)12-2759-03

1设计问题的提出

1.1对于最短路径问题

最短路径是在实际应用中非常有用的工具，将该问题细分，可以分为点到点最短路径，单源点的最短路径，所有点到所有点以及带负边情况下的最短路径。

1.2 Dijkstra算法的主要思想

Dijkstra算法的基本思路是：假设每个点都有一对标号(dj, pj)，其中dj是从起源点s到点j的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：

1)初始化。起源点设置为：①ds=0, ps为空;②所有其他点: di=∞, pi=;③标记起源点s，记k=s,其他所有点设为未标记的。

2)检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：dj=min［dj, dk+lkj］式中，lkj是从点k到j的直接连接距离。

3)选取下一个点。从所有未标记的结点中，选取dj中最小的一个i：di=min［dj,所有未标记的点j］点i就被选为最短路径中的一点，并设为已标记的。

4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j* 5)标记点i。……