资源描述：
《狄克斯特拉算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、狄克斯特拉算法目录简介算法依据算法的步骤应用举例编辑本段简介 狄克斯特拉算法亦即最短路径搜索法，是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959年提出，它被公认为是最好的路径搜索法之一。编辑本段算法依据 若从S点到T点有一条最短的路径，则该路径上的任何点到S的距离都是最短的。如上图，A到C的最短路径为A——E——C，可以看出来其路径上的一点如E到C的最短距离也在A——E——C这条路径上。 对于这种很简单的图我们可以通过穷举比较法很容易得到最短路径。但是对于大规模的网络图，比如大城市的道
2、路网络。这样的话我们就很难一眼看出来最短路径了。这时要用计算机根据狄克斯特拉算法计算最短路径了。编辑本段算法的步骤 1、狄克斯特拉算法将所有的顶点分为S,T两类：S用来存放已知最短路径的顶点。而T存放未知最短路径的顶点。如果起始点（假设上图的v1为起始点）到某个顶点（相邻点）的最短距离已经求出，比如A——B的距离。那么就把B归入S，其余的不能直接算出最短距离的则要归入T。 刚开始的S只有起始点一个，随着算法的继续，首先将起始点相邻的点归入到S，知道最后一点——目标点归入S。 2、在起始点与相邻点的路径中选
3、择一个最短的，然后将这个相邻点设为起始点，重复上一步（注意，不能回退到第一个起始点，只能递接下去）。直到所有的点都归为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）相比，如果前者小，那么就将这个标记
4、点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的距离。用这个距离
5、跟起始点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＋
6、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
