狄克斯特拉算法.doc

狄克斯特拉算法目录简介 算法依据 算法的步骤 应用举例编辑本段简介狄克斯特拉算法亦即最短路径搜索法，是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959年提出，它被公认为是最好的路径搜索法之一。 编辑本段算法依据 若从S点到T点有一条最短的路径，则该路径上的任何点到S的距离都是最短的。如上图，A到C的最短路径为AEC，可以看出来其路径上的一点如E到C的最短距离也在AEC这条路径上。 对于这种很简单的图我们可以通过穷举比较法很容易得到最短路径。但是对于大规模的网络图，比如大城市的道路网络。这样的话我们就很难一眼看出来最短路径了。这时要用计算机根据狄克斯特拉算法计算最短路径了。 编辑本段算法的步骤1、狄克斯特拉算法将所有的顶点分为S,T两类：S用来存放已知最短路径的顶点。而T存放未知最短路径的顶点。如果起始点（假设上图的v1为起始点）到某个顶点（相邻点）的最短距离已经求出，比如AB的距离。那么就把B归入S，其余的不能直接算出最短距离的则要归入T。 刚开始的S只有起始点一个，随着算法的继续，首先将起始点相邻的点归入到S，知道最后一点目标点归入S。 2、在起始点与相邻点的路径中选择一个最短的，然后将这个相邻点设为起始点，重复上一步（注意，不能回退到第一个起始点，只能递接下去）。直到所有的点都归为S为止。 3、用公式表示如下 另d（x，y）表示点x到y的距离，D（x）表示x到起始点的距离。 对起始点S做标记，且对所有起始点D（x）为无穷大。对所有为做标记的点按以下公式计算距离 D(x)=min(D(X) d(x,y)+D(y) 其中y是最后一个标记的点。也就是与起始点的距离已知的那个点。 上述这个公式的表示，D(X)要和D（x，y）+D（y）相比，如果前者小，那么就将这个标记点y去掉。路径直接为起始点到x。否则，路径要经过y。 编辑本段应用举例如上图，通过狄克斯特拉算法求出v1到v7的最短距离 1、首先将A做为起始点进行标记。算出v1到相邻各点的距离。 D(B)=4 D(C)= D(D)=1 D(E)=2 最小值为D(D)=1，所以将D点做标记。 2、因为D(D)最小，所以将D进行标记，重复上个步骤。来计算D(B),D(C),D(E) D(B)=min(D(B),d(D,B)+D(D)=min(4,+1)=4 其中D(B)表示起始点A到B的距离。用这个距离跟起始点A经过D再到B的距离d(D,B)+D(D)相比，如D(B)比较小，则舍弃D点，路径将不经过D点。这是理解算法的关键。 同理得D(C)=min(D(C),d(D,C)+D(D)=min(,9+1)=10 D(E)=min(D(E),d(D,E)+D(D)=min(2,2+1)=2 这里D（E）最小，所以取E点为标记点。且因为起始点A到E的距离比ADE的短，所以将D点舍去。 3、对E做标记，计算D(B),D(C) D(B)min(D(B),d(E,B)D(E)min(4,12)3 D(C)min(D(C),d(E,C)D(E)min(10,62)8 最小值为D(B)3。去B为标记点，且因为AEB的距离比AB的距离短，所以将E点保留。 4、对B作标记，计算D(C) D(