算法可视化
入门执行逻辑
Floyd:所有点对最短路
依次允许经过第 0、1、2、3 号节点中转,逐步更新所有点对之间的距离,最后得到任意两点间的最短距离。
main.cpp第 1 行
1// Floyd: 允许经过前 k 个节点中转, 更新所有点对距离
2for (int k = 0; k < n; k++)
3 for (int i = 0; i < n; i++)
4 for (int j = 0; j < n; j++)
5 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
6// dist[0][3] = 6
变量表0 个变量
还没有变量,执行到声明语句后出现
DP 表格(行=前 i 个物品, 列=容量)
| 0 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 1 | 0 | 3 | 8 | 99 |
| 2 | 3 | 0 | 2 | 5 |
| 3 | 8 | 2 | 0 | 1 |
| 3 | 99 | 5 | 1 | 0 |
本格取物品本格不取最优路径
1/18
初始距离矩阵:直接相连的边有长度,没有边的是 ∞。dist[0][3] 目前是 ∞
1 / 18