AI题库 · GESP-C++八级题库
题目分享 #20604
下列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;
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。