简答题 偏难
#22599

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

(最短路径问题)无向连通图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;

}

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p>(1)v=-1</p><p>(2)dist[i]&lt;dist[v] 或 dist[v]&gt;dist[i] 或 dist[i]&lt;=dist[v] 或 dist[v]&gt;=dist[i]</p><p>(3)v=i</p><p>(4)used[v]=1</p><p>(5)dist[v]+w[v][i]&lt;dist[i] 或 dist[i]&gt;dist[v]+w[v][i] 或 dist[v]+w[v][i]&lt;=dist[i] 或 dist[i]&gt;=dist[v]+w[v][i]</p>
这道题暂未补解析。