# Todai Entrance Exam: Subject 2019 – Problem 3

**(1)** Apply the Algorithm of (2), we get shortest paths:

**(2)**

**(3)** Inside block **if**, add: .

**(4)** There are 2 loops in the algorithm. The loop traversing the set is inside the loop traversing the set , so the time complexity is .

**(5)** According to Wikipedia:

Vertices are visited once and before we visit a vertice, we must perform the operation finding the vertice with minimum tentative distance, which would cost if we use a binary heap as a data structure.

Edges are visited once and after we visit an edge, we must perform the operation editing the tentative distance of the vertice, which would cost if we use a binary heap as a data structure.

Therefore, the time complexity of implementing Dijkstra using binary heap is .