Todai Entrance Exam: Subject 2019 – Problem 3

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

    \[ s \rightarrow v_{4} = 6 \]

    \[ s \rightarrow v_{4} \rightarrow v_{2} \rightarrow v_{1} \rightarrow v_{3} = 2 \]

    \[ s \rightarrow v_{4} \rightarrow v_{2} = 4 \]

    \[ s \rightarrow v_{4} \rightarrow v_{2} \rightarrow v_{1} = 1 \]

(2)

    \[ (A) = u.d + d_{uv} \]

(3) Inside block if, add: v.pre = u.

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

(5) According to Wikipedia:

For every updates to the tentative distance, it would cost O(\log_{2}|V|). Each edge is visited once and each vertice is visited once, so the time complexity can be either O(|V|\log_{2}|V|) or O(|E|\log_{2}|V|) depending which one is worse.

Therefore, the time complexity of implementing Dijkstra using binary heap is O((|E| + |V|)\log_{2}|V|).


Facebooktwitterredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *