想了半天,还不如画个图看看最直观😂
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 500;
int n, m;
int dist[N];//储存i结点到源点的距离
int g[N][N];//领接矩阵存边
bool st[N];//标记i结点的最短路是否确定即是否找到了源点到当前点的最短距离
//求源点到n点的最短路,不存在返回-1
int dijkstra() {
memset(dist, 0x3f, sizeof dist);//初始时定义dist无穷大
dist[1] = 0;//源点到源点距离为0
for (int i = 0; i < n - 1; i++) {
int t = -1; // 存储当前访问的点
for (int j = 1; j <= n; j++) {//遍历dist数组,找到没有确定最短路径的节点中距离源点最近的点t
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j; //更新
}
//遍历所有i可到达的点j
//如果dist[j]大于dist[i]+i,j相连的边g[i][j],则更新dist[j]=dist[i]+g[i][j]
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;//标记,该点路径已确定
}
}
if (dist[n] == -1) return -1;//不存在最低路径
else return dist[n];
}
int main() {
cin >> n >> m;
memset(g, 0x3f, sizeof g);//初始化图,因为求最短路径,所以设置为无穷大
while (m--) {
int x, y, z;
cin >> x >> y >> z;
g[x][y] = min(g[x][y], z); //重复边中保取最小边
}
printf("%d", dijkstra());
return 0;
}