QQ扫一扫联系
(最短路径问题)无向连通图 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; }