(1) Apply the Algorithm of (2), we get shortest paths:
(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 .