最短路径的弗洛伊德算法
实现计算有向图没有负权回路的的任何点对的最短路径程序输入的有向图示#include iostream #include vector #include queue #include unordered_set #include climits #include unordered_map using namespace std; void shortestpath_FLOYD(int n, long long (a)[4][4], int(path)[4][4], int(Edge)[4][4]) { for (int i 0; i n; i) //初始化数组a 和path for (int j 0; j n; j) { a[i][j] Edge[i][j]; if (i ! j a[i][j] std::numeric_limitsfloat::max()) path[i][j] i; //vi 与vj 之间有弧 else path[i][j] 99999; } for (int k 0; k n; k) //计算每一对顶点之间的A( k )值 for (int i 0; i n; i) for (int j 0; j n; j) if (a[i][k] a[k][j] a[i][j]) { a[i][j] a[i][k] a[k][j]; path[i][j] path[k][j]; } } void printshortestPath_printlength(long long acopy[][4], int pathcopy[][4],int source , int target) { std::cout The shortest path from source to target is: std::endl; std::cout (acopy[source][target]) std::endl; if (acopy[source][target] INT_MAX) { std::cout INT_MAX stands for the fact that source can not reach target ! std::endl; } else { std::cout The path is : std::endl; std::cout target --; while (pathcopy[source][target] ! source) { std::cout pathcopy[source][target] --; target pathcopy[source][target]; } std::cout pathcopy[source][target] endl; } std::cout End std::endl; } int main() { int source; int target; int n 4; int Edge[4][4] { {0,1,INT_MAX,4}, {INT_MAX,0,9,2}, {3,5,0,8}, {INT_MAX, INT_MAX,INT_MAX,0}, // 实验 3--2 没有 链路 }; int path[4][4] { -1 }; long long a[4][4] { 0 }; std::cout sizeof(long long) endl; std::cout Enter the source: std::endl; cin source; std::cout Enter the target: std::endl; cin target; shortestpath_FLOYD(n,a,path,Edge); std::cout The ultimate matrix a is : std::endl; for (int i0 ; i4 ; i ) for (int j 0; j 4; j) { std::cout a[i][j] ; if (j 3) { std::cout endl; } } std::cout The ultimate path matrix is : std::endl; for (int i 0; i 4; i) for (int j 0; j 4; j) { std::cout path[i][j] ; if (j 3) { std::cout endl; } } printshortestPath_printlength(a, path, source, target); }结果说明最终的最短距离矩阵中 如果值为INT_MAX 2147483647 表示 点对之间无路径可通最终输出的路径矩阵 path表示点对 path[i][j] 中回溯的上一个节点点对自己的回溯无实际意义用path[i][i] 99999特殊标识 表示
)
