A51350. (最短路径问题)无向连通图 G 有 n 个结点，依次编号为 0,1,2,…,(n−1)。用邻接矩阵的形式给出每条边的边长,要求输出以结点 0 为起点出发,到各结点的最短路径长度。使用 Dijkstra 算法解决该问题：利用 dist 数组记录当前各结点与起点的已找到的最短路径长度;每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展，更新与 v 相邻的结点的 dist 值；不断进行上述…
填空题
较易
知识点
题目描述
(最短路径问题)无向连通图 G 有 n 个结点，依次编号为 0,1,2,…,(n−1)。用邻接矩阵的形式给出每条边的边长,要求输出以结点 0 为起点出发,到各结点的最短路径长度。
使用 Dijkstra 算法解决该问题：
利用 dist 数组记录当前各结点与起点的已找到的最短路径长度;
每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展，更新与 v 相邻的结点的 dist 值；
不断进行上述操作直至所有结点均被扩展，此时 dist 数据中记录的值即为各结点与起点的最短路径长度。
参考答案
<p>1.v=-1</p><p><br/></p><p>2.dist[i] < dist[v]</p><p><br/></p><p>3.v=i</p><p><br/></p><p>4.used[v] = 1</p><p><br/></p><p>5.dist[v] + w[v][i] < dist[i]</p>
上一题
下一题