首页 › 题库 › GESP编程能力等级认证 › 6.2 最短路径

GESP-C++八级 题库

共 5 道题 · 按题型筛选,点「查看答案」核对解析
章节 6.2 最短路径 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.2 最短路径

下面是使用邻接矩阵实现的Dijkstra算法的核心片段,用于求单源最短路径。在找到当前距离起点最近的顶点u 后,需要更新其邻接点 j 的距离。横线处应填入的代码是( )。

for (int j = 1; j <= n; j++) { 
    if (!visited[j] && graph[u][j] < INF) { 
      if (________) { // 在此处填入选项 
        dis[j] = dis[u] + graph[u][j]; 
      } 
    } 
}
A
dis[j] < dis[u] + graph[u][j]
B
dis[j] > dis[u] + graph[u][j]
C
graph[u][j] > dis[u] + dis[j]
D
dis[j] > graph[u][j]
答案与解析
正确答案:B
在Dijkstra算法中,选定当前距离起点最近的未处理顶点u后,需遍历其所有邻接点j。对于每个邻接点j,若存在从u到j的边且通过u到达j的路径长度小于当前记录的最短距离,则更新j的最短距离。该判断条件基于比较经由u到达j的路径长度与原记录距离的大小关系,仅当新路径更短时执行更新操作。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.2 最短路径

下面Floyd算法中,横线处应该填入的是?( )

#include <iostream>
using namespace std;
#define N 21
#define INF 99999999
int map[N][N];
int main() {
    int n, m, t1, t2, t3;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)
                map[i][j] = 0;
            else
                map[i][j] = INF;
        }
    }
    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2 >> t3;
        map[t1][t2] = t3;
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (map[i][j] > map[i][k] + map[k][j])
                    ________; // 在此处填入选项
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout.width(4);
            cout << map[i][j];
        }
        cout << endl;
    }
}
A
map[i][j] = map[i][k] + map[k][j]
B
map[i][k] = map[i][j] - map[k][j]
C
map[i][j] = map[i][k] - map[k][j]
D
map[k][j] = map[i][j] - map[i][k]
答案与解析
正确答案:A

根据 Floyd 算法,如果 i 到 k 加上 k 到 j 的最短路长度小于当前 i 到 j 的最短路长度,则用前者更新后者。 (图论算法: Floyd 算法)

题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.2 最短路径

下列Dijkstra算法中,横线处应该填入的是( )。

typedef struct Edge {
	int in, out; // 从下标in顶点到下标out顶点的边
	int len; // 边长度
	struct Edge * next;
} Edge;
// v:顶点个数,graph:出边邻接表,start:起点下标,dis:输出每个顶点的最短距离
void dijkstra(int v, Edge * graph[], int start, int * dis) {
	const int MAX_DIS = 0x7fffff;
	for (int i = 0; i < v; i++)
		dis[i] = MAX_DIS;
	dis[start] = 0;
	int * visited = new int[v];
	for (int i = 0; i < v; i++)
		visited[i] = 0;
	visited[start] = 1;
	for (int t = 0; ; t++) {
		int min = MAX_DIS, minv = -1;
		for (int i = 0; i < v; i++) {
			if (visited[i] == 0 && min > dis[i]) {
				min = dis[i];
				minv = i;
			}
		}
		if (minv < 0)
			break;
		visited[minv] = 1;
		for (Edge * e = graph[minv]; e != NULL; e = e->next) {
			________; // 在此处填入选项
		}
	}
	delete[] visited;
}
A
if (dis[e->out] > e->len)
	dis[e->out] = e->len;
B
if (dis[e->out] > min + e->len)
	dis[e->out] = min + e->len;
C
if (dis[e->in] > e->len)
	dis[e->in] = e->len;
D
if (dis[e->in] > min + e->len)
	dis[e->in] = min + e->len;
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.2 最短路径

下列Dijkstra算法中,横线处应该填入的是( )。

#include <iostream>
using namespace std;

#define N 100
int n, e, s;
const int inf = 0x7fffff;
int dis[N + 1];
int cheak[N + 1];
int graph[N + 1][N + 1];
int main() {
	for (int i = 1; i <= N; i++)
		dis[i] = inf;
	cin >> n >> e;
	for (int i = 1; i <= e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a][b] = c;
	}
	cin >> s;
	dis[s] = 0;
	for (int i = 1; i <= n; i++) {
		int minn = inf, minx;
		for (int j = 1; j <= n; j++) {
			if (__________) { // 在此处填入选项
				minn = dis[j];
				minx = j;
			}
		}
		cheak[minx] = 1;
		for (int j = 1; j <= n; j++) {
			if (graph[minx][j] > 0) {
				if (minn + graph[minx][j] < dis[j]) {
					dis[j] = minn + graph[minx][j];
				}
			}
		}
	}
}
A
dis[j] > minn && cheak[j] == 0
B
dis[j] < minn && cheak[j] == 0
C
dis[j] >= minn && cheak[j] == 0
D
dis[j] < minn && cheak[j] != 0
答案与解析
正确答案:B

朴素dijkstra算法,在非负权图中,用cheak[]标记已经求得最短路的点(因为已经求得,所以后续不会再更新),每次选择距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx,由非负权图的原因,该节点minxj将加入已经求得最短路的点的集合,同时用minx尝试是否能更新S到其他待球节点的最短路。横线处就是求解距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx的,因此选B。

题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.2 最短路径

下面Floyd算法中,横线处应该填入的是( )。

#include <iostream>
using namespace std;

#define N 21
#define INF 99999999
int map[N][N];
int main() {
	int n, m, t1, t2, t3;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				map[i][j] = 0;
			else
				map[i][j] = INF;
		}
	}
	for (int i = 1; i <= m; i++) {
		cin >> t1 >> t2 >> t3;
		map[t1][t2] = t3;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (__________) // 在此处填入选项
					map[i][j] = map[i][k] + map[k][j];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout.width(4);
			cout << map[i][j];
		}
		cout << endl;
	}
}
A
map[i][j] < map[i][k] + map[k][j]
B
map[i][j] > map[i][k] + map[k][j]
C
map[i][j] > map[i][k] - map[k][j]
D
map[i][j] < map[i][k] - map[k][j]
答案与解析
正确答案:B

Floyd算法本质是个DP,或者可以理解为松弛操作:

i和j的最短路如果可以通过中间节点k做更新:

则需要map[i][j]>map[i][k]+map[k][j];选B。

题目详情