当前位置：首页 > news >正文

力扣算法刷题 Day 64 Floyd算法 A* 算法总结篇

news 2026/5/10 0:02:43

Floyd算法

算法原理

Floyd算法解决多源最短路径问题。本质用动态规划。如,mindis[1][5] = mindis[1][3] + mindis[3][5]

算法流程

dp五部曲：

dp数组含义： dp[i][j]表示从i到j的最短距离。
递推式：dp[i][j] = min(dp[i][k] + dp[k][j])， k需要遍历
初始化：dp[i][i] = 0,如果i到j有边,dp[i][j] = 权值，否则为正无穷
遍历顺序：三层循环

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;constlonglongINF=1e18;voidfloyd(vector<vector<longlong>>&dist){intn=dist.size();for(intk=0;k<n;k++){// 中转点for(inti=0;i<n;i++){// 起点for(intj=0;j<n;j++){// 终点if(dist[i][k]==INF||dist[k][j]==INF){continue;}dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);}}}}intmain(){intn,m;cin>>n>>m;vector<vector<longlong>>dist(n,vector<longlong>(n,INF));// 自己到自己距离为 0for(inti=0;i<n;i++){dist[i][i]=0;}// 输入 m 条边：u v w// 表示 u 到 v 的边权为 wfor(inti=0;i<m;i++){intu,v;longlongw;cin>>u>>v>>w;dist[u][v]=min(dist[u][v],w);// 如果是无向图，加上这一句// dist[v][u] = min(dist[v][u], w);}floyd(dist);// 输出最短距离矩阵for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(dist[i][j]==INF){cout<<"INF ";}else{cout<<dist[i][j]<<" ";}}cout<<endl;}return0;}

当需要打印出所有路径时：
优化：开两个数组，一个存距离，一个存下一跳。path[i][j]表示从i到j的路径上，以i为起点的下一跳是什么。还原时不断寻找下一跳为起点的path。如：path[1][4] = 2 -> path[2][4] = 3-> path[3][4] = 4 ，到达终点，停止。

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;constlonglongINF=1e18;voidfloydWithPath(vector<vector<longlong>>&dist,vector<vector<int>>&path){intn=dist.size();for(intk=0;k<n;k++){// 中转点for(inti=0;i<n;i++){// 起点for(intj=0;j<n;j++){// 终点if(dist[i][k]==INF||dist[k][j]==INF){continue;}if(dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];// i 到 j 的下一跳，应该等于 i 到 k 的下一跳path[i][j]=path[i][k];}}}}}vector<int>getPath(intstart,intend,constvector<vector<int>>&path){vector<int>result;if(path[start][end]==-1){returnresult;// 不可达}result.push_back(start);while(start!=end){start=path[start][end];result.push_back(start);}returnresult;}intmain(){intn,m;cin>>n>>m;vector<vector<longlong>>dist(n,vector<longlong>(n,INF));vector<vector<int>>path(n,vector<int>(n,-1));// 初始化for(inti=0;i<n;i++){dist[i][i]=0;path[i][i]=i;}// 输入 m 条边：u v w// 表示 u 到 v 的边权为 wfor(inti=0;i<m;i++){intu,v;longlongw;cin>>u>>v>>w;if(w<dist[u][v]){dist[u][v]=w;path[u][v]=v;}// 如果是无向图，加上下面这一段/* if (w < dist[v][u]) { dist[v][u] = w; path[v][u] = u; } */}floydWithPath(dist,path);// 输出最短距离矩阵cout<<"Shortest distance matrix:"<<endl;for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(dist[i][j]==INF){cout<<"INF ";}else{cout<<dist[i][j]<<" ";}}cout<<endl;}// 查询一条路径intstart,end;cout<<"Input start and end: ";cin>>start>>end;vector<int>shortestPath=getPath(start,end,path);if(shortestPath.empty()){cout<<"No path from "<<start<<" to "<<end<<endl;}else{cout<<"Shortest path: ";for(inti=0;i<shortestPath.size();i++){if(i>0)cout<<" -> ";cout<<shortestPath[i];}cout<<endl;cout<<"Shortest distance: "<<dist[start][end]<<endl;}return0;}

A* 算法

算法原理

改良版的BFS。区别于穷举，A* 根据启发式函数有选择的进行遍历。给每一个节点一个权值，Key = 起点到当前节点的距离 + 当前节点到终点的距离。维护BFS队列，每次从中取权值最小的节点。

#include<iostream>#include<queue>#include<string.h>usingnamespacestd;intmoves[1001][1001];intdir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};intb1,b2;// F = G + H// G = 从起点到该节点路径消耗// H = 该节点到终点的预估消耗structKnight{intx,y;intg,h,f;booloperator<(constKnight&k)const{// 重载运算符， 从小到大排序returnk.f<f;}};priority_queue<Knight>que;intHeuristic(constKnight&k){// 欧拉距离return(k.x-b1)*(k.x-b1)+(k.y-b2)*(k.y-b2);// 统一不开根号，这样可以提高精度}voidastar(constKnight&k){Knight cur,next;que.push(k);while(!que.empty()){cur=que.top();que.pop();if(cur.x==b1&&cur.y==b2)break;for(inti=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);}}}}intmain(){intn,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;}return0;}