Dijkstra单源最短路(邻接矩阵存图+路径记录)

#include<iostream> using namespace std; const int maxn = 1010; //最大顶点数 const int inf = 0x3f3f3f3f; //无穷大 bool vis[maxn]; //标记当前点是否访问过 int pre[maxn]; //父节点 int m[maxn][maxn]; //邻接矩阵 int dis[maxn]; //最短路 int n,e; //输入的顶点数 和边数 int u,v,w; void Dijkstra(int cost[][maxn],int lowcost[],int n,int beg){ //cost为传入的图(邻接矩阵形式),lowcost为传入的dis(存最短路径),n为点的个数,beg为起始点 for(int i = 0;i < n;i++){ //初始化 lowcost[i] = inf; //距离为无穷大 vis[i] = false; pre[i] = -1; } lowcost[beg] = 0; //起点到自己的距离为0 for(int j = 0;j < n;j++){ int k = -1; int minn = inf; //与prim类似 寻找最小的那一条边 for(int i = 0;i < n;i++){ if(!vis[i] && lowcost[i]<minn){ //比较一下 k = i; minn = lowcost[i]; } } if(k == -1){ break; } vis[k] = true; //标记已经访问过 for(int i = 0;i < n;i++){ //更新距离(松弛) if(!vis[i] && lowcost[i] > lowcost[k] + cost[k][i]){ //如果经过k点再到i点的距离比直接到i点的距离要短 //就要松弛 lowcost[i] = lowcost[k] + cost[k][i]; //记录父节点 pre[i] = k; } } } /* for(int i = 0;i < n;i++) cout << dis[i] << " "; cout << endl; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++) cout << m[i][j] << " "; cout << endl; } */ } void dispath(int n){//displaypath(显示路径) n为到达的点 显示从起点到n的最短路径 if(n != -1){ dispath(pre[n]); cout << n; } //cout << pre[n]; return; } int main() { cin >> n; for(int i = 0;i < n;i++){ for(int j = i + 1;j < n;j++){ m[i][j] = m[j][i] = inf; } } cin >> e; while(e--){ cin >> u >> v >> w; m[u][v] = m[v][u] = w; } /* for(int i = 0;i < n;i++){ for(int j = i + 1;j < n;j++){ m[i][j] = m[j][i] = inf; } } */ Dijkstra(m,dis,n,0); for(int i = 0;i < n;i++) cout << dis[i] << " "; cout << endl; cout << "输入查询的点:"; cin >> n; dispath(n); /* cout << pre[1]; cout << pre[2]; cout << pre[0]; */ return 0; }