弗洛伊德(Floyd)算法

typedef Seqlist VertexSet;
ShortestPath_Floyd(AdjMartrix g, 
                   WeightType dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM]),
                   VertexSet path[MAX_VERTEX_NUM][MAX_VERTEX_NUM]) {
/*g为带权有向图的邻接矩阵表示发，path[i]vi到vj的当前最短路径，
dist[i][j]为vi到vj的最短路径长度*/
    for(i = 0; i < g.vexnum; i++) {     //初始化dist[i][j]和path[i][j]
        for(j = 0; j < g.vexnum; j++) {
            InitList(&p[i][j]);
            dist[i][j] = g.arcs[i][j].adj;
            if(dist[i][j] < INFINITY) {
                AddTail(&path[i][j], g.vertex[i]);
                AddTail(&path[i][j], g.vertex[j]);
            }
        }
    }
    for(k = 0; k < g.vexnum; k++) {
        for(i = 0; i < g.vexnum; i++) {
            for(j = 0; j <g.vexnum; j++) {
                if(dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist = dist[i][k] + dist[k][j];
                    path = JoinList(path[k][i], path[i][j]);
                }//End if JoinList合并顺序表操作
            } //End for(j) 
        } //End for(i) 
    } //End for(k) 
}