浅谈Floyd算法

弗洛伊德算法是用于求解无负权回路的图的任意一对顶点间最短路径的算法，该算法采用的基本思想是动态规划（转移方程就是cost[j] = cost[k] + cost[k][j] < cost[j] ? cost[k] + cost[k][j] : cost[j]）
算法步骤：令初始邻接矩阵matrix[][]为cost[][]，对于每个顶点k，检查以此为中转顶点，对每对顶点i和j，若cost[k] + cost[k][j] < cost[j]则更新cost[j] = cost[k] + cost[k][j]，并且同时记录下这个中转的顶点k于path[j]中，检查完每个顶点即可
代码如下
[code]// 复用数据结构邻接矩阵，见 https://www.cnblogs.com/RodneyTang/p/19010305void floyd(adjMaxtrix &mGraph, int **&path, int **&cost){    path = (int **)malloc(sizeof(int *) * mGraph.vnum);    cost = (int **)malloc(sizeof(int *) * mGraph.vnum);    for (int i = 0; i < mGraph.vnum; ++i)        path = (int *)malloc(sizeof(int) * mGraph.vnum);    for (int i = 0; i < mGraph.vnum; ++i)        for (int j = 0; j < mGraph.vnum; ++j)        {            path[j] = -1;            cost[j] = mGraph.matrix[j];        }    for (int k = 0; k < mGraph.vnum; ++k)        for (int i = 0; i < mGraph.vnum; ++i)            for (int j = 0; j < mGraph.vnum; ++j)                if (cost[k]  ... -> k ... -> v，这样递归地查找和的中间顶点即可，规定path[j] = -1时无中间顶点，即路径是i -> j</p>这个算法的时空复杂度都很显然，不必多说

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除