Floyd算法 C语言实现

Floyd算法 C语言实现 算法思想

维护一个当前最短举例矩阵lowcost，lowcost[i][j]表示当前从i到j的最短距离，初始为图的邻接矩阵，此后对该矩阵进行n（图中节点的个数）次迭代，第k次迭代的过程为，对lowcost[i][j]进行更新，考虑从节点i到节点j经过第k个节点，距离是否减小，若减小，则更新lowcost矩阵，具体为比较lowcost[i][k]+lowcost[k][j]与lowcost[i][j]，并且用path[i][j]将路径保存

代码

#define MAX_VEXNUM 100
typedef struct{
    int vex[MAX_VEXNUM];
    int edge[MAX_VEXNUM][MAX_VEXNUM];
    int vexnum,edgenum;
}MGraph;//矩阵存储图
void floyd(MGraph G,int path[][MAX_VEXNUM]){//path[i][j]=k表示从i到j的最短路径经过k
    int lowcost[MAX_VEXNUM][MAX_VEXNUM];
    for(int i=0;itmp){
                    lowcost[i][j]=tmp;
                    path[i][j]=path[i][k];
                }
            }
        }
    }
}