迪杰斯特拉算法用来解决从顶点v0出发到其余顶点的最短路径,该算法按照最短路径长度递增的顺序产生所以最短路径。
对于图G=(V,E),将图中的顶点分成两组:
第一组S:已求出的最短路径的终点集合(开始为{v0})。
第二组V-S:尚未求出最短路径的终点集合(开始为V-{v0}的全部结点)。
算法将按最短路径长度的递增顺序逐个将第二组的顶点加入到第一组中,直到所有顶点都被加入到第一组顶点集S为止。
扩展资料:
从dis数组选择最小值,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,此时完成一个顶点,需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在dis中的值。 然后,又从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点。
参考资料来源:百度百科-Dijkstra算法