文章目录
- Floyd 算法精讲
- A * 算法精讲 （A star算法）
Floyd 算法精讲
题目链接
文章讲解
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int n, m;cin >> n >> m; // 输入图的节点数n和边数m// grid[i][j][k] 表示从节点i到节点j，在使用前k个节点作为中间节点的情况下的最短距离// 初始化为一个大值10005，表示初始状态下的路径都是不可达的vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));// 读取所有边的信息，存储到 grid 数组中for (int i = 0; i < m; i++) {int x, y, z;cin >> x >> y >> z; // 读取一条边，起点为x，终点为y，边的权重为zgrid[x][y][0] = z; // 初始化权值，表示直接连接的路径grid[y][x][0] = z; // 因为是无向图，双向存储}// Floyd-Warshall 算法的主循环，计算最短路径// k 表示考虑的中间节点，i 和 j 是起点和终点for (int k = 1; k <= n; k++) { // 遍历每个可能的中间节点kfor (int i = 1; i <= n; i++) { // 遍历起点ifor (int j = 1; j <= n; j++) { // 遍历终点j// 递推公式：// 1. 从 i 到 j 的最短路径可以通过中间节点k更新// 2. 选择两种情况中的最小值：// - 经过节点k，min(grid[i][k][k-1] + grid[k][j][k-1])// - 不经过节点k，保持原有的最短路径grid[i][j][k-1]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; // 输入查询的起点和终点// 判断最终的最短路径是否仍然是大值10005，表示不可达if (grid[start][end][n] == 10005) {cout << -1 << endl; // 如果不可达，输出 -1} else {cout << grid[start][end][n] << endl; // 输出从 start 到 end 的最短路径}}return 0;
}A * 算法精讲 （A star算法）
题目链接
文章讲解
#include<iostream>
#include<queue>
#include<string.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}; // 定义骑士的8个移动方向int b1, b2; // 目标位置（终点）// F = G + H
// G = 从起点到该节点路径消耗
// H = 该节点到终点的预估消耗// Knight结构体，表示骑士的当前位置、路径消耗和估算消耗
struct Knight{int x, y; // 当前坐标int g, h, f; // g为从起点到当前节点的路径消耗，h为从当前节点到终点的估算消耗，f为总代价bool operator < (const Knight & k) const { // 重载运算符，使得优先队列按 f 值从小到大排序return k.f < f; // f值越小，优先级越高}
};priority_queue<Knight> que; // 优先队列，用于A*算法选择下一个最优节点// 估算函数，计算从当前位置到终点的欧几里得距离（不用开根号提高效率）
int Heuristic(const Knight& k) { return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2); // 不开根号，加速计算
}// A*算法的主体部分
void astar(const Knight& k)
{Knight cur, next; // 当前节点和下一个节点que.push(k); // 将起点放入优先队列while(!que.empty()) // 当队列不为空时{cur = que.top(); // 取出队列中的最优节点（f最小的节点）que.pop(); // 弹出最优节点if(cur.x == b1 && cur.y == b2) // 如果当前节点就是目标节点break; // 找到目标，退出循环// 遍历骑士的8个方向for(int i = 0; i < 8; i++){next.x = cur.x + dir[i][0]; // 根据当前方向计算下一个位置的x坐标next.y = cur.y + dir[i][1]; // 根据当前方向计算下一个位置的y坐标// 判断下一个位置是否越界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; // 记录到达next的步数// 开始计算f值（f = g + h）next.g = cur.g + 5; // 设定每步的路径消耗为5（骑士每次都走“日”字形）next.h = Heuristic(next); // 计算到目标的估算消耗next.f = next.g + next.h; // 计算f值（总代价）que.push(next); // 将新的节点加入优先队列}}}
}// 主函数
int main()
{int n, a1, a2;cin >> n; // 输入测试用例数量while (n--) { // 处理每个测试用例cin >> a1 >> a2 >> b1 >> b2; // 输入起点和终点的坐标memset(moves, 0, sizeof(moves)); // 初始化moves数组，表示所有城市都没有被访问Knight start; // 创建起点start.x = a1; // 起点的x坐标start.y = a2; // 起点的y坐标start.g = 0; // 起点的g值为0，因为到自己不需要路径start.h = Heuristic(start); // 计算起点到终点的估算消耗start.f = start.g + start.h; // 计算起点的f值astar(start); // 执行A*算法来找到最短路径while(!que.empty()) que.pop(); // 清空队列，以准备下一次的计算cout << moves[b1][b2] << endl; // 输出从起点到终点的最短路径步数}return 0;
}
