最短路径算法 一）Floyed-Warshall算法 时间：O(N3) 初始化：点u、v如果有边相连，则dis[u][v]=w[u][v]。 如果不相连则dis[u][v]=0x7fffffff For (k = 1; k <= n; k++) For (i = 1; i <= n; i++) For (j = 1; j <= n; j++) If (dis[i][j] >dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j]; 算法结束：dis[i][j]得出的就是从i到j的最短路径。 用Floyed求出任两点间的最短路，然后求出每个点到所有可达的点的最大距离，记做mdis[i]。（Floyed算法） r1=max(mdis[i]) 然后枚举不连通的两点i,j，把他们连通，则新的直径是mdis[i]+mdis[j]+(i,j)间的距离。 r2=min(mdis[i]+mdis[j]+dis[i,j]) re=max(r1,r2) re就是所求。 二）Dijkstra算法 时间：O (N2) ps::不能处理存在负边权 初始化：dis[v]=∞(v≠s); dis[s]=0; pre[s]=0; For (i = 1; i <= n ; i++) 1.在没有被访问过的点中找一个顶点u使得dis[u]是最小的。 2.u标记为已确定最短路径 3.For 与u相连的每个未确定最短路径的顶点v if (dis[u]+w[u][v] < dis[v]) { dis[v] = dis[u] + w[u][v]; pre[v] = u; } 三）Bellman-Ford算法 时间：O(NE) O(NE)，N是顶点数，E是边数。 设s为起点，dis[v]即为s到v的最短距离，pre[v]为v前驱。w[j]是边j的长度，且j连接u、v。 初始化：dis[s]=0,dis[v]=∞（v≠s），pre[s]=0 For (i = 1; i <= n-1; i++) For (j = 1; j <= E; j++) //注意要枚举所有边，不能枚举点。 if (dis[u]+w[j]<dis[v]) //u、v分别是这条边连接的两个点。 { dis[v] =dis[u] + w[j]; pre[v] = u; }
对于求最短路径的方法，理解算法的思路选用最短时间，无疑是最根本的方法，学会套用算法，理解是一方面，用又是一方面学以致用才行。
