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) = d_{u} + 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:

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 O(\log_{2}|V|) 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 O(\log_{2}|V|) if we use a binary heap as a data structure.

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


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

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