最短路径之狄克斯特拉（Dijkstra）算法

相比较贝尔曼-福特算法需要每次对所有边进行松弛操作，时间复杂度为O（顶点数*边数），并且可以处理负权边，但是我们在实际生活中，计算路径的时候，极少遇到负权边的情况，所以只考虑正权边的情况下，可以采用更优化的Dijkstra算法。

Dijkstra算法设置了两个集合，设所有顶点集合为V，则：

S=所有与起点s已经确定最短路径、最低权重值的顶点。

W=V-S。

算法每次都将W中权重值最小的顶点u移入S中，并对u的所有边进行松弛操作。

看图说话：

初始化：

S=A0W=B∞，C∞,D∞,E∞,F∞,G∞

1、需要对A的所有边进行松弛操作，结果

S=A0W=B6，C4,D∞,E∞,F∞,G∞

2、取出W中最小的顶点C放入S，并对C所有边进行松弛操作，结果

S=A0，C4W=B6，D9，E∞，F11，G∞

3、取出W中最小顶点B放入S，并对B所有边进行松弛操作，结果

S=A0，B6，C4W=D9，E11，F11，G∞

4、取出W中最小的顶点D放入S，并对D所有边进行松弛操作，结果

S=A0，B6，C4，D9W=E11，F10，G∞

5、取出W中最小的顶点F放入S，并对F所有边进行松弛操作，结果

S=A0，B6，C4，D9，F10W=E11，G∞

6、取出W中最小的顶点E放入S，并对E所有边进行松弛操作，结果

S=A0，B6，C4，D9，E11，F10W=G∞

7、取出W中最小的顶点G放入S，并对G所有边进行松弛操作，结果

S=A0，B6，C4，D9，E11，F10，G∞

至此，我们可以得出一个最短路径树：

A——B=6A——C=4A——C——D=9A——B——E=11A——C——D——F=10A无法到达G

在这里有两个地方可以优化：

1、因为要取出权重最小的顶点，所以每次都要对W进行排序，采用遍历数组进行比较的算法，不如采用优先队列（PriorityQueue），因为优先队列采用了堆结构，排序时间复杂度是O (nlgn)。

2、如果我们只是想计算起点到某点的最短距离，那么在遍历的时候，检查一下取出的最小顶点是否是终点，如果是，跳出循环即可。

更多相关文章