source 源端, target目的端
1.构造n*n的相邻矩阵, -1表示未相邻
int matrix[n][n]
int dist[n] 初始化各节点直接到source的距离, dist[source] = 0;
bool visited[n] 是否访问过
dist[source] = 0;
for(int i = 0;i<n-1;i++) {
//找剩余n-1个节点的距离
int min = INT32_MAX;
int midx = 0;
for(int j = 0;j<n;j++){
//对每个节点判断是否已访问,并找到未访问的距离最短的点
if (!visited[j] && dist[j] < min){
min = dist[j];
midx = j;
}
}
visited[midx] = true;
dist[midx] = min;
//对未被访问的节点,通过midx节点为桥梁,更新dist数组
for (int j = 0; j < n; ++j) {
if (!visited[j] && matrix[midx][j] > 0){
dist[j] = min(dist[j], dist[midx] + matrix[midx][j]);
}
}
//不断访问节点,直到所有节点都访问过后,退出循环。
}
标签:dist,int,dijkstra,最短,source,算法,节点
From: https://www.cnblogs.com/sanguoasd/p/17472721.html