大网站建设_家居设计网站推荐_山西百度查关键词排名_企业查询平台

之前提到的dijkstra算法和Bellman算法都是只能有一个起点，而这题是求多个起点到多个终点的多条最短路径。Floyd算法的思想是动态规划。
dp数组，grid[i][j][k] = m，表示 节点i 到 节点j 以[1…k] 集合中的一个节点为中间节点的最短距离为m。
dp方程，节点i 到 节点j 的最短路径是否经过节点k。若经过，grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]；若不经过，grid[i][j][k] = grid[i][j][k - 1]。所以，递推方程为grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])

#include <iostream>
#include <vector>
#include <list>
using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));  // 因为边的最大距离是10^4for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2][0] = val;grid[p2][p1][0] = val; }// 开始 floydfor (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);}}}// 输出结果int z, start, end;cin >> z;while (z--) {cin >> start >> end;if (grid[start][end][n] == 10005)cout << -1 << endl;elsecout << grid[start][end][n] << endl;}
}

空间优化，减少dp数组的一个维度，代码如下：

#include <iostream>
#include <vector>
using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid(n + 1, vector<int>(n + 1, 10005));  // 因为边的最大距离是10^4for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2] = val;grid[p2][p1] = val; }// 开始 floydfor (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);}}}// 输出结果int z, start, end;cin >> z;while (z--) {cin >> start >> end;if (grid[start][end] == 10005)cout << -1 << endl;elsecout << grid[start][end] << endl;}
}

BFS 是没有目的性的 一圈一圈去搜索， 而 A * 是有方向性的去搜索，这个是A算法和BFS最本质的区别。A的方向由启发性函数决定，这部分代码之后补上。