MAXV 是图中最大结点数的上限，设置为100。
w[MAXV][MAXV] 是邻接矩阵，用于存储结点之间的边长，w[i][j] 表示从结点 i 到结点 j 的边的长度。如果 i 和 j 之间没有边，则值为 -1。
dist[MAXV] 存储从起点（结点0）到每个结点的最短路径长度。
used[MAXV] 是标记数组，用于记录结点是否已确定最短距离。0 表示未确定，1 表示已确定。

输入与初始化

读取结点数 n 以及邻接矩阵 w 的值，表示图中的边长信息。
dist[0] = 0，设置起点结点0到自身的距离为0。
对于其他结点，初始化 dist[i] = -1，表示起点到这些结点的初始距离为无穷大（用 -1 代替），表示未到达。
初始化 used[i] = 0，表示所有结点都还未被处理过。

主循环部分

v = -1;：初始化当前最小距离结点的索引为 -1，表示还没有找到合适的结点。
在 for 循环中，程序寻找未处理且距离最短的结点 v。如果当前没有结点满足条件（例如所有结点都已处理），则 v 保持为 -1。
一旦找到合适的 v，如果 v == -1（即找不到未处理的结点），则跳出循环，算法结束。
used[v] = 1;：标记结点 v 为已处理，表示它的最短路径已经确定。
然后，更新与 v 相邻的所有结点的最短路径值。如果 dist[v] + w[v][i] < dist[i]，则说明通过 v 可以找到一条到达结点 i 的更短路径，于是更新 dist[i] 的值。

输出结果

#include <iostream>
using namespace std;
const int MAXV = 100;
int n, i , j, v;
int w[MAXV][MAXV]; // 邻接矩阵，记录边长
// 其中 w[i][j] 为连接结点 i 和结点 j 的无向边长度，若无边则为 -1
int dist[MAXV];  //存储0点到其它结点的最短路径长度
int used[MAXV]; // 记录结点是否已确定最短距离（0：未确定；1：已确定）
int main() {
    cin >> n;  //n为结点数
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            cin >> w[i][j]; //录入边长
    dist[0] = 0;  //0点到自身的距离为0
    for (i = 1; i < n; i++)
        dist[i] = -1; 
    //初始化所有结点距离
    for (i = 0; i < n; i++)
        used[i] = 0;
    //初始化所有结点为未扩展状态
    while (true) {
        v=-1 ;
        for (i = 0; i < n; i++)
            if (used[i] != 1 && dist[i] != -1 && (v == -1 || dist[i]<dist[v] ))
            //v刚开始赋的是-1，意思是还没找到距离最近的点，在循环里满足判断条件的第一个点i，
            //会赋给v（因为v==-1是在||左边的，当||左边为真时右边不参与运算，不会越界）
            v=i;
        if(v == -1)
            break;
        used[v]=1;
        for (i = 0; i < n; i++)
            if (w[v][i] != -1 && (dist[i] == -1 || dist[v]+w[v][i]<dist[i] ))
                dist[i] = dist[v] + w[v][i];
        //依次更新每个点所到相邻的点路径值
    }
    for (i = 0; i < n; i++)
        cout << dist[i] << endl;
    return 0;
}

Previous Topic

Back to Lesson

Next Topic