# 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:

For every updates to the tentative distance, it would cost . Each edge is visited once and each vertice is visited once, so the time complexity can be either or depending which one is worse.

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