狄克斯特拉算法.docVIP

狄克斯特拉算法 目录简介 算法依据 算法的步骤 应用举例 编辑本段简介 　　狄克斯特拉算法亦即最短路径有哪些信誉好的足球投注网站法，是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959年提出，它被公认为是最好的路径有哪些信誉好的足球投注网站法之一。 编辑本段算法依据 　　 ?? ?? 若从S点到T点有一条最短的路径，则该路径上的任何点到S的距离都是最短的。如上图，A到C的最短路径为A——E——C，可以看出来其路径上的一点如E到C的最短距离也在A——E——C这条路径上。 　　对于这种很简单的图我们可以通过穷举比较法很容易得到最短路径。但是对于大规模的网络图，比如大城市的道路网络。这样的话我们就很难一眼看出来最短路径了。这时要用计算机根据狄克斯特拉算法计算最短路径了。 编辑本段算法的步骤 　　1、狄克斯特拉算法将所有的顶点分为S,T两类：S用来存放已知最短路径的顶点。而T存放未知最短路径的顶点。如果起始点（假设上图的v1为起始点）到某个顶点（相邻点）的最短距离已经求出，比如A——B的距离。那么就把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的距离比A——D——E的短，所以将D点舍去。 　　3、对E做标记，计算D(B),D(C) 　　D(B)＝min(D(B),d(E,B)＋D(E))＝min(4,1＋2)＝3 　　D(C)＝min(D(C),d(E,C)＋D(E))＝min(10,6＋2)＝8 　　最小值为D(B)＝3。去B为标记点，且因为A——E——B的距离比A——B的距离短，所以将E点保留。 　　4、对B作标记，计算D(C) 　　D(C)＝min(D(C),d(B,C)＋D(B))＝min(8,7＋3)＝8 　　因为D(C)小于d(B,C)+D(B),所以将B点舍去。 　　综上，路径为A——E——C