教怎么做ppt的网站,手机网站开发 图库类,frontpage网站模板下载,写一篇软文1000字Floyd 算法
重点#xff1a;多源最短路径算法#xff0c;前的最短路径算法是单源的也就是只有一个起点。递推每个节点之间最短的路径
时间复杂度#xff1a; O(n^3)空间复杂度#xff1a;O(n^2)
#include iostream
#include vector
using namespace std…Floyd 算法
重点多源最短路径算法前的最短路径算法是单源的也就是只有一个起点。递推每个节点之间最短的路径
时间复杂度 O(n^3)空间复杂度O(n^2)
#include iostream
#include vector
using namespace std;int main() {int n, m, p1, p2, val;cin n m;vectorvectorint grid(n 1, vectorint(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;else cout grid[start][end] endl;}
}A * 算法
重点Astar关键在于启发式函数,也就是影响广搜或者 dijkstra 从容器队列里取元素的优先顺序
#includeiostream
#includequeue
#includestring.h
using namespace std;
int moves[1001][1001];
int dir[8][2]{-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
int b1, b2;
// F G H
// G 从起点到该节点路径消耗
// H 该节点到终点的预估消耗struct Knight{int x,y;int g,h,f;bool operator (const Knight k) const{ // 重载运算符 从小到大排序return k.f f;}
};priority_queueKnight que;int Heuristic(const Knight k) { // 欧拉距离return (k.x - b1) * (k.x - b1) (k.y - b2) * (k.y - b2); // 统一不开根号这样可以提高精度
}
void astar(const Knight k)
{Knight cur, next;que.push(k);while(!que.empty()){curque.top(); que.pop();if(cur.x b1 cur.y b2)break;for(int i 0; i 8; i){next.x cur.x dir[i][0];next.y cur.y dir[i][1];if(next.x 1 || next.x 1000 || next.y 1 || next.y 1000)continue;if(!moves[next.x][next.y]){moves[next.x][next.y] moves[cur.x][cur.y] 1;// 开始计算Fnext.g cur.g 5; // 统一不开根号这样可以提高精度马走日1 * 1 2 * 2 5next.h Heuristic(next);next.f next.g next.h;que.push(next);}}}
}int main()
{int n, a1, a2;cin n;while (n--) {cin a1 a2 b1 b2;memset(moves,0,sizeof(moves));Knight start;start.x a1;start.y a2;start.g 0;start.h Heuristic(start);start.f start.g start.h;astar(start);while(!que.empty()) que.pop(); // 队列清空cout moves[b1][b2] endl;}return 0;
}总结
Floyd算法本质是动态规划递推算出每个节点之间的最短距离。可以用于有负权值的最短路径。
Astar 是一种 广搜的改良版。 有的是 Astar是 dijkstra 的改良版。
