29-算法设计

2.5.2　算法设计

Dijkstra 算法是解决单源最短路径问题的贪心算法，它先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出从源点到其他各个顶点的最短路径。

Dijkstra算法的基本思想是首先假定源点为u，顶点集合V被划分为两部分：集合S和 V−S。初始时 S 中仅含有源点 u，其中 S 中的顶点到源点的最短路径已经确定。集合V−S中所包含的顶点到源点的最短路径的长度待定，称从源点出发只经过S中的点到达V−S中的点的路径为特殊路径，并用数组dist[]记录当前每个顶点所对应的最短特殊路径长度。

Dijkstra算法采用的贪心策略是选择特殊路径长度最短的路径，将其连接的V−S中的顶点加入到集合S中，同时更新数组dist[]。一旦S包含了所有顶点，dist[]就是从源到所有其他顶点之间的最短路径长度。

（1）数据结构。设置地图的带权邻接矩阵为map[][]，即如果从源点u到顶点i有边，就令 map[u][i]等于<u，i>的权值，否则 map[u][i]=∞（无穷大）；采用一维数组 dist[i]来记录从源点到i顶点的最短路径长度；采用一维数组p[i]来记录最短路径上i顶点的前驱。

（2）初始化。令集合S={u}，对于集合V−S中的所有顶点x，初始化dist[i]=map[u][i]，如果源点u到顶点i有边相连，初始化p[i]=u，否则p[i]= −1。

（3）找最小。在集合V−S中依照贪心策略来寻找使得dist[j]具有最小值的顶点t，即dist[t]=min（dist[j]|j属于V−S集合），则顶点t就是集合V−S中距离源点u最近的顶点。

（4）加入S战队。将顶点t加入集合S中，同时更新V−S。

（5）判结束。如果集合V−S为空，算法结束，否则转（6）。

（6）借东风。在（3）中已经找到了源点到t的最短路径，那么对集合V−S中所有与顶点t相邻的顶点j，都可以借助t走捷径。如果dis[j]>dist[t]+map[t][j]，则dist[j]=dist[t]+map[t][j]，记录顶点j的前驱为t，有p[j]= t，转（3）。

由此，可求得从源点u到图G的其余各个顶点的最短路径及长度，也可通过数组p[]逆向找到最短路径上经过的城市。