「漫步计算机系统」之数据结构与算法（27）：图的最短路径

大家好，欢迎来到IT知识分享网。

图的路径：从任一顶点开始，由边的邻接关系构成的有限长顶点序列，称为路径；

路径长度：路径中边的数目；

简单路径：除第一个和最后一个顶点，路径中无重复出现的顶点，称为简单路径；

环：路径中第一个顶点和最后一个顶点相同；

图的最短路径：在有向图中，从源点到终点有多条路径，其中权的和最小的路径称为最短路径。

Dijkstra算法

典型的单源最短路径算法，计算某个顶点到其他所有顶点的最短路径。基本思想：从源点开始，找到离源点最近的顶点前进，然后以该顶点为中心，得到源点到其他所有顶点的最短路径。

步骤：

1. 将图中所有顶点分为两个集合，源点和离源点路径最短的顶点在集合P中，除此之外的顶点在集合Q中。初始只有源点在P中；
2. 在Q中找到一个顶点u，其离源点最近，加入集合P中；
3. 不断从Q中找离P中顶点最近的顶点，加入P中，直到集合Q为空；
4. 最终离源点最近的所有路径都找到，算法结束。

实例：以顶点1为源点，找到最短路径。

初始，P={1}，Q={2, 3, 4, 5, 6}；

1. 顶点1可达2、3，到2最短；路径为<1, 2>，2加入P；P={1, 2}, Q={3, 4 , 5, 6}；
2. 从P={1, 2} 到 Q={3, 4 , 5, 6}，路径<1, 2, 4>最短，4加入P；P={1, 2, 4}，Q={3, 5, 6}；
3. 从P={1, 2, 4} 到 Q={3, 5, 6}，路径<1, 2, 4, 3>最短，3加入P；P={1, 2, 4, 3}，Q={5, 6}；
4. 从P={1, 2, 4, 3} 到 Q={5, 6}，路径<1, 2, 4, 3, 5>最短，5加入P；P={1, 2, 4, 3, 5}，Q={6}；
5. 从P={1, 2, 4, 3, 5} 到 Q={6}，路径<1, 2, 4, 3, 5, 6>最短，6加入P；P={1, 2, 4, 3, 5, 6}，Q为空集，算法结束。

因此，以1为源点，

到达2的最短路径为<1, 2>，

到达4的最短路径为<1, 2, 4>，

到达3的最短路径为<1, 2, 4, 3>，

到达5的最短路径为<1, 2, 4, 3, 5>，

到达6的最短路径为<1, 2, 4, 3, 5, 6>。

至此，数据结构部分已完结，接下来讲解算法。

注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。