最短路径

最短路径长度（分为有权值和无权值，无权值的最短路径长度是路径上经过的边的数目，有权值的最短路径是经过的边的权值之和）；
求图的最短路径问题包括两个方面：一是求图中一顶点到其余各顶点的最短路径；二是求图中每对顶点之间的最短路径。
求一顶点到其余各顶点的最短路径的算法：迪克特斯拉（Dijkstra）
具体思路：按照从源点到其余每一顶点的最短路径长度的升序依次从源点求出从源点到各顶点的最短路径及长度，每次求出从源点i到一个终点m的最短路径长度后，都要以该顶点m作为新考虑的中间点，用Vi到Vm的最短路径和最短路径长度对Vi到其他尚未求出最短路径的那些终点的当前最短路径及长度做必要的修改，使之成为当前新的最短路经合最短路径长度，当进行n-2次后，求出n-2个顶点的最短路径，除源点外，剩余的一个顶点的最短路径已经确定下来。每循环一次确定一个最短路径点。
求每对顶点之间的最短路径的算法：（1）对每个顶点为源点进行n次迪克斯特拉算法，因迪克斯塔拉的时间复杂度为o(n^2)，所以此方法的时间复杂度为o(n^3)；（2）弗洛伊德（Floyed）算法