文档介绍：:..狄克斯特拉算法目录简介算法依据算法的步骤应用举例编辑本段简介狄克斯特拉算法亦即最短路径搜索法,是由荷兰计算机科学家狄克斯特拉(Dijkstra)于1959年提出,它被公认为是最好的路径搜索法之一。编辑本段算法依据若从S点到T点有一条最短的路径,则该路径上的任何点到S的距离都是最短的。如上图,A到C的最短路径为A E C,可以看出来其路径上的一点如E到C的最短距离也在A——E——C这条路径上。对于这种很简单的图我们可以通过穷举比较法很容易得到最短路径。但是对于大规模的网络图,比如大城市的道路网络。这样的话我们就很难一眼看出来最短路径了。这吋要用计算机根据狄克斯特拉算法计算最短路径了。编辑本段算法的步骤1、狄克斯特拉算法将所有的顶点分为S,T两类:S用来存放已知最短路径的顶点。而T存放未知最短路径的顶点。如果起始点(假设上图的vl为起始点)到某个顶点(相邻点)的最短距离已经求出,比如A——B的距离。那么就把B归入S,其余的不能直接算出最短距离的则要归入T。刚开始的S只有起始点一个,随着算法的继续,首先将起始点相邻的点归入到S,知道最后一点—冃标点归入So2、在起始点与相邻点的路径中选择一个最短的,然后将这个相邻点设为起始点,重复上一步(注意,不能回退到第一个起始点,只能递接下去)。直到所有的点都归为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。编辑本段应用举例如上图,通过狄克斯特拉算法求出vl到v7的最短距离1、首先将A做为起始点进行标记。算出vl到相邻各点的距离。D(B)=4D(C)=°°D(D)=1D(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到