PROBLEM SET
最短路径
按知识点筛选题目，系统巩固该考点。
题目列表
共 61 题
A63401
在一个3×3的正方形棋盘中，有8个正方形棋子，分别标着数字1~8，还有一个空位。 在游戏过程中，可以把空位上、下、左、右四个相邻位置的棋子移到空位上来，每步只能移动1个棋子。目标状态如下图所示： 下面是一个例子，从初始状态开始，经过3步可达到目标状态，如下图所示：从下图的初始状态开始，要达到目标状态，需要移动的最小步数是（ ）。
计算思维组
--
--
A66191
某公司新出了⼀款⽆⼈驾驶的⼩汽车，通过声控智能驾驶系统，乘客只要告诉汽车⽬的地，车⼦就能⾃动 选择⼀条优化路线，告诉乘客后驶达那⾥。请问下⾯哪项不是驾驶系统完成选路所必须的。
2023年
--
--
A66826
要求出简单有向图中从顶点A到顶点B的最短路径，在深度优先搜索和广度优先搜索中选择，广度优先更适 合。( )
2024年
--
--
A66814
下面的程序使用邻接矩阵表达的带权无向图，则从顶点0到顶点3的最短距离为（ ）。1 int weight[4][4] = {
2024年
--
--
A68628
使用迪杰斯特拉（Dijkstra）算法，求图中从顶点1到其他各顶点的最短路径，得到各最短路径的目标顶点依次是（ ）。
2024年
--
--
A66682
下列Dijkstra算法中，横线处应该填入的是（ ）。#include <iostream>
2024年
--
--
A67579
下面Floyd算法中，横线处应该填入的是（ ）。1 #include <iostream>
2025年
--
--
A67570
3.1 编程题 1
2025年
--
--
A67462
求解下图中A点到D点最短路径，其中A到B之间的12可以理解为距离。求解这样的问题常用Dijkstra算法，其 思路是通过逐步选择当前距离起点最近的节点来求解非负权重图（如距离不能为负值）单源最短路径的算法。从该 算法的描述可以看出，Dijkstra算法是贪心算法。
2025年
--
--
A67416
下面的程序使用邻接矩阵表达的带权无向图，则从顶点0到顶点3的最短距离为（ ）。int weight[4][4] = {
2025年
--
--
A67260
货物运输
2025年
--
--
A67229
下列Dijkstra算法 ，假设图graph 中顶点数 v、 边数 e ，则程序的时间复杂度为（ ）。
2025年
--
--
A67225
下面的C++程序使用出边邻接表表达的带权无向图，则从顶点0到顶点3的最短距离为（ ）。
2025年
--
--
A67208
下面是使用邻接矩阵实现的Dijkstra算法的核心片段，用于求单源最短路径。在找到当前距离起点最近的顶点 u 后，需要更新其邻接点 j 的距离。横线处应填入的C++代码是（ ）。for (int j = 1; j <= n; j++) {
2025年
--
--
A67173
城市规划
2025年
--
--
A67873
在使用 Dijkstra 算法求单源最短路径时，如果发现某条边被选入从源点出发的最短路径生成树中，那么这条边也一定属于该图的某棵最小生成树。
2026年
--
--
A67863
对于含n个顶点（n≥2）的连通加权有向图，若图中不存在负权环，则任意两点之间的最短路径（简单路径）最多包含（ ）条边。
2026年
--
--
A67862
在使用Floyd算法求任意两点间最短路径时，时间复杂度为O(V3)。若在某次算法执行前，已经用 Dijkstra 算法正确求出了所有点对的最短路并存入了 dist 数组。如果此时继续对该 dist 数组执行一次完整的 Floyd 算法过程（无任何提前终止），执行完毕后 dist 数组内的值（ ）。
2026年
--
--
A67861
下列代码试图实现Floyd算法求所有点对之间的最短路径，横线处应填入（ ）。1 void floyd(int n, int dist[][MAXN]) {
2026年
--
--
A67851
消息查找
2026年
--
--