GESP 八级 · GESP 202412 C++ 八级 第 12 题

下列 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;

根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

1. 🎯 考纲定位

【考点】贪心策略｜最短路径算法｜指针遍历

八级图论核心考点——Dijkstra算法松弛步骤。命题人卡住的是考生对"最短路径递推本质"的理解：只背"更新距离"结论的人，会误选A（忽略min）或C/D（用错顶点），掉入贪心策略里"必须加上当前顶点最短距离"这一细节陷阱。

2. 🧠 解题思维

看到横线在 for (Edge * e = graph[minv]; ...) 里——当前顶点minv已确定最短距离min，要遍历其出边更新邻居。核心观察：最短路径满足递推关系：从起点到e->out的最短距离 = min + 边权。因此判断条件必须是dis[e->out] > min + e->len，且更新目标只能是e->out（出边指向的顶点）。