图的单源最短路径算法 (二)

// 初始化
for (i = 0; i < n; i ++) {
dis[i] = map[src][i];
mark[i] = 0;
}

dis[src] = 0;
mark[src] = 1;

// n-1次主循环，每次循环求得src到某个顶点v的最短路径
for (i = 1; i < n; i ++) {
min = MAX;
k = src;
for (j = 0; j < n; j ++) {
if (!mark[j] && dis[j] < min) {
k = j;
min = dis[j];
}
}
mark[k] = 1;

// 更新src到其它各顶点的最短路径
for (j = 0; j < n; j ++) {
tmp = map[k][j] + dis[k];
if (tmp < dis[j] && mark[j] == 0) {
dis[j] = tmp;
}
}
}
}