最短路径问题

无向连通图 G 有 n 个结点，依次编号为 0,1,2,…,(n−1)。用邻接矩阵的形式给出每条边的边长，要求输出以结点 0 为起点出发，到各结点的最短路径长度。

使用 Dijkstra 算法解决该问题：利用 dist 数组记录当前各结点与起点的已找到的最短路径长度；每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展，更新与 v 相邻的结点的 dist 值；不断进行上述操作直至所有结点均被扩展，此时 dist 数据中记录的值即为各结点与起点的最短路径长度。（第五空 2 分，其余 3 分）

#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]; int used[MAXV]; // 记录结点是否已扩展（0：未扩展；1：已扩展） 
int main() { 
    cin >> n; 
    for (i = 0; i < n; i++) 
        for (j = 0; j < n; j++) 
            cin >> w[i][j]; 
dist[0] = 0;
for (i = 1; i < n; i++) 
        dist[i] = -1; 
    for (i = 0; i < n; i++) 
        used[i] = 0; 
    while (true) { 
            (1)    ; 
        for (i = 0; i < n; i++) 
            if (used[i] != 1 && dist[i] != -1 && (v == -1 ||     (2)    )) 
                    (3)    ; 
        if (v == -1) 
            break; 
            (4)    ; 
        for (i = 0; i < n; i++) 
            if (w[v][i] != -1 && (dist[i] == -1 ||     (5)    )) 
                dist[i] = dist[v] + w[v][i]; 
    } 
    for (i = 0; i < n; i++) 
        cout << dist[i] << endl; 
    return 0; 
}

1. ①处应填（ ）{{ select(1) }}

• V=0
• V=-1
• dist[v]=1
• dist[v]=0

2. ②处应填（ ）{{ select(2) }}

• dist[v]!=-1
• v==n-1
• used[i]!=1
• dist[i]<=dist[v]

3. ③处应填（ ）{{ select(3) }}

• used[i]=1
• used[v]=1
• v++
• v=i

4. ④处应填（ ）{{ select(4) }}

• w[v][v]=0
• w[v][v]=1
• used[v]=1
• dist[v]++

5. ⑤处应填（ ）{{ select(5) }}

• !used[v]
• !used[i]
• dist[v]-dist[i]+(used[i]==1)<=w[v][i]
• dist[v]+w[v][i]<=dist[i]