完善程序-2解析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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;
}
Scroll to Top