最短路径

对于一个顶点数为N的有向网路图，我们可以通过前面所提到的单源最短路径算法执行N次来获得每一对顶点间的最短路径。这种方法的时间复杂度为O（N*N*N）。如果网络中有负权值的边，则需要使用前面提到的单源最短路径算法之Bellman—Floyd算法。总之，总可以通过单源最短路径来求得每对顶点间的最短路径。这里我就不再用程序实现上述方法,下面介绍Floyd解决这一问题的另一种算法，它形式简单，利于理解，而且时间复杂度同样为O（N*N*N）。        Floyd算法是根据给定有向网络的邻接矩阵dist[n][n]来求顶点vi到顶点vj的最短路径。这一算法的基本思想是：假设vi和vj之间存在一条路径，但这并不一定是最短路径，试着在vi和vj之间增加一个中间顶点vk。 若增加vk后的路径(vi, vk, vj) 比(vi, vj)短，则以新的路径代替原路径，并且修改dist[i][j]的值为新路径的权值；若增加vk后的路径比(vi, vj)更长，则维持dist[i][j]不变。然后在修改后的dist矩阵中，另选一个顶点作为中间顶点，重复以上的操作，直到除vi和vj顶点的其余顶点都做过中间顶点为止 。