東京大学 情報理工学系研究科 コンピュータ科学専攻 2017年8月実施 専門科目I 問題1
Author
Description
Consider the problem of finding the shortest paths in a weighted directed graph using Dijkstra’s algorithm. Denote the set of vertices as
Answer the following questions:
(1) Depict an example input data (with
(2) Below is a pseudo-code of the algorithm that computes the length
Dijkstra(graph G = (V, E), start node s, length d(u, v) of each edge (u,v)) {
c = an empty array; Q = an empty set;
for (v in V)
c[v] = ∞;
c[s] = 0;
for (v in V)
add v to Q;
while (Q is not empty) {
v = a vertex v in Q that minimizes c[v]; // (i)
remove v from Q; // (i)
for (u in {destinations of edges outgoing from v})
[ blank a ] // (ii)
}
}
(3) Consider the following graph with while
statement when the above algorithm is applied to the graph.

(4) For each of the code fragments (i) and (ii) in the above pseudo-code, answer the total time spent in the code fragment during the whole run of the algorithm, using big
(5) One can reduce the computational complexity of the algorithm by using a priority queue (binary heap) as
Kai
(1)
s -- 3 -- a
\ /
4 -3
\ /
b
Dijkstra will find that the shortest path to
(2)
if (c[v] + d(v,u) <= c[u]) {
c[u] = c[v] + d(v,u);
}
(3)
(4)
Each vertex is added to and removed from
(5)
We will keep vertices in a heap, ordered by
- Building the heap takes
- Looking up a minimum takes
(i, line 1) - Removing minimum takes
(i, line 2) - in (ii), we need to decrease key of an element in a heap. It takes
To conclude (i) takes