厦门 网站建设企业邮箱,做网站搭建需要什么人,班级网站 php,网页游戏网站模板目录
介绍#xff1a;
代码#xff1a;
结果#xff1a;
介绍#xff1a;
弗洛伊德算法#xff08;Floyd algorithm#xff09;也称为Floyd-Warshall算法#xff0c;是一种用于求解所有节点对之间的最短路径的动态规划算法。它使用了一个二维数组来存储所有节点…目录
介绍
代码
结果
介绍
弗洛伊德算法Floyd algorithm也称为Floyd-Warshall算法是一种用于求解所有节点对之间的最短路径的动态规划算法。它使用了一个二维数组来存储所有节点之间的最短距离该数组的初始值为节点之间的直接距离或无穷大。然后算法对数组进行多次迭代每次迭代都尝试通过一个中间节点更新节点之间的距离值直到所有节点之间的最短距离被计算出来。该算法的时间复杂度为O(n^3)适用于有向图或无向图但不能处理带有负权边的图。 代码
#includeiostream//弗洛伊德算法
using namespace std;
int G[100][100],D[100][100],Path[100][100];
int n, t, maxlen999;
void Floyd()
{for (int i 0; i n; i)//初始化最短路径和前驱for(int j0; jn; j){D[i][j] G[i][j];if (D[i][j] maxlen i ! j)//i和j之间有弧前驱设为iPath[i][j] i;else//i和j之间无弧前驱设为-1Path[i][j] -1;}for(int k0;kn;k)for(int i0;in;i)for (int j 0; j n; j){if (D[i][k] D[k][j] D[i][j])//i到j经过k点有更短路径{D[i][j] D[i][k] D[k][j];//更新D[i][j]Path[i][j] Path[k][j];//更改前驱}}for (int i 1; i n; i)//访问从0点到各点的最短距离{cout 0点到 i 的最短路径权值为 D[0][i] ;cout 路径为;int a Path[0][i];cout i ;while (a ! 0){cout a ;a Path[0][a];}cout endl;}
}
int main()
{cout 输入顶点数 endl;cin n;for (int i 0; i n; i)for (int j 0; j n; j)G[i][j] maxlen;cout 输入边数 endl;cin t;for (int i 0; i t; i){int v1, v2, w;cin v1 v2 w;G[v1][v2] w;}Floyd();
}
结果
