下列 Dijkstra 算法（每轮线性扫描找最小、出边邻接表松弛），顶点数 v、边数 e，其时间复杂度为：
void dijkstra(int v, Edge * graph[], int start, int * dis) {
// 初始化 dis[], visited[]
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)
if (dis[e->out] > e->len) dis[e->out] = e->len;
}
}
- A. O(v²)
- B. O((v+e)·log v)
- C. O(v+e)
- D. O(v·e)
正确答案：A