有一天，孩子回来对我说：“妈妈，听说马尔代夫很不错，放假了我想去玩。”马尔代夫？我也想去！没有人不向往一场说走就走的旅行！“其实我想去的地方很多，呼伦贝尔大草原、玉龙雪山、布达拉宫、艾菲尔铁塔……”小孩子还说着他感兴趣的地方。于是我们拿出地图，标出想去的地点，然后计算最短路线，估算大约所需的时间，有了这张秘制地图，一场说走就走的旅行不是梦！
“哇，感觉我们像凡尔纳的《环游地球八十天》，好激动！可是老妈你也太out了，学计算机的最短路线你用手算？”
暴汗……，“小子你别牛，你知道怎么算？”
“呃，好像是叫什么迪杰斯特拉的人会算。”
哈哈，关键时刻还要老妈上场了！
根据题目描述可知，这是一个求单源最短路径的问题。给定有向带权图G =（V，Ｅ），其中每条边的权是非负实数。此外，给定V中的一个顶点，称为源点。现在要计算从源到所有其他各顶点的最短路径长度，这里路径长度指路上各边的权之和。
如何求源点到其他各点的最短路径呢？
如图9所示，迪杰斯特拉（Edsger Wybe Dijkstra），荷兰人，计算机科学家。他早年钻研物理及数学，后转而研究计算学。他曾在1972年获得过素有“计算机科学界的诺贝尔奖”之称的图灵奖，与Donald Ervin Knuth并称为我们这个时代最伟大的计算机科学家。
Dijkstra 算法是解决单源最短路径问题的贪心算法，它先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出从源点到其他各个顶点的最短路径。
Dijkstra算法的基本思想是首先假定源点为u，顶点集合V被划分为两部分：集合S和 V-S。初始时 S 中仅含有源点 u，其中 S 中的顶点到源点的最短路径已经确定。集合V-S中所包含的顶点到源点的最短路径的长度待定，称从源点出发只经过S中的点到达V-S中的点的路径为特殊路径，并用数组dist[]记录当前每个顶点所对应的最短特殊路径长度。
Dijkstra算法采用的贪心策略是选择特殊路径长度最短的路径，将其连接的V-S中的顶点加入到集合S中，同时更新数组dist[]。一旦S包含了所有顶点，dist[]就是从源到所有其他顶点之间的最短路径长度。
① 数据结构
设置地图的带权邻接矩阵为map[][]，即如果从源点 u 到顶点 i 有边，就令 map[u][i] 等于 (u，i) 的权值，否则 map[u][i]=∞（无穷大）；采用一维数组 dist[i]来记录从源点 u 到 i 顶点的最短路径长度；采用一维数组p[i]来记录最短路径上 i 顶点的前驱。
② 初始化
令集合S={u}，对于集合V-S中的所有顶点x，初始化dist[i]=map[u][i]，如果源点u到顶点i有边相连，初始化p[i]=u，否则p[i]= -1。
③ 找最小
在集合V-S中依照贪心策略来寻找使得dist[j]具有最小值的顶点 t，即dist[t]=min(dist[j] | j属于V-S集合)，则顶点 t 就是集合V-S中距离源点 u 最近的顶点。
④ 加入S战队
将顶点 t 加入集合S中，同时更新V-S。
⑤ 判断是否计算结束
如果集合V-S为空，算法结束，否则转⑥。
⑥ 借东风
在③中已经找到了源点到 t 的最短路径，那么对集合V-S中所有与顶点 t 相邻的顶点 j，都可以借助 t 走捷径。如果dist[j]>dist[t] map[t][j]，则dist[j]=dist[t] map[t][j]，记录顶点 j 的前驱为 t，有p[j]= t，转③。
由此，可求得从源点 u 到图G的其余各个顶点的最短路径及长度，也可通过数组 p[] 逆向找到最短路径上经过的城市。
3 完美图解现在我们有一个景点地图，如图10所示↓，假设从1号结点出发，求到其他各个结点的最短路径。
算法步骤如下。
3.1 数据结构
设置地图的带权邻接矩阵为map[][]，即如果从顶点 i 到顶点 j 有边，则map[i][j]等于(i，j)的权值，否则map[i][j]=∞（无穷大），如图11所示↑。
3.2 初始化
令集合S={1}，V-S={2，3，4，5}，对于集合V-S中的所有顶点 x，初始化最短距离数组dist[i]=map[1][i]，dist[u]=0，如图12所示↓。如果源点1到顶点i有边相连，初始化前驱数组p[i]=1，否则p[i]= -1，如图13所示↓。
