Learn
Exam

Dijkstra Algorithm

Difficulty
INTERMEDIATE

Problem

Given the number of vertices n and directed edge information stored in edges, write a solution function to return the length of the shortest path from vertex 1 to vertex n.

Concept Explanation

Dijkstra's Algorithm is an algorithm used to find the shortest path from a fixed starting vertex to other vertices in a given graph. To apply Dijkstra's Algorithm, the graph's edge weights (costs) must all be positive, and the time complexity of the algorithm is O(Elog⁡2V)O(E \log_2 V).

The working mechanism of Dijkstra's Algorithm is as follows: First, assume the following directed graph is given.
image1

Let's calculate the shortest path distances from vertex 1 to the other vertices, storing them in Dist[]. Initially, we set the distance to all vertices except vertex 1 as INF.

image2

Next, based on the edges starting from vertex 1, we update the shortest path distances in Dist for other vertices.

image3

Afterward, among the unvisited vertices (vertices 2, 3, 4, 5), we visit the vertex with the smallest distance in Dist and repeat the same process. In this example, we visit vertex 3 and update Dist based on its edge information.

image4

Next, among the unvisited vertices (vertices 2, 4, 5), we visit vertex 2 with the smallest Dist value and update Dist.

image5

Repeating this process to visit and update all vertices, we complete the algorithm. By using a priority queue to implement this algorithm, the time complexity becomes O(Elog⁡2V)O(E \log_2 V).

image6

Constraints

  • The number of vertices n is a natural number between 2 and 10,000 inclusive.
  • The directed edge information edges has between 1 and 2,000,000 elements.
  • Each element in edges consists of x, y, and w, where:
    • x, y are natural numbers between 1 and n inclusive.
    • w is a natural number between 1 and 10,000 inclusive.
  • The edge information guarantees that there exists a path from vertex 1 to vertex n.

Test Case

Test Case Number n edges return
1 5 [[1,2,3],[3,5,1],[1,5,10],[4,5,3],[2,4,1],[3,4,4],[1,3,2]] 3
2 8 [[5,8,4],[4,8,4],[3,4,8],[4,5,4],[2,3,3],[7,5,8],[3,7,2],[3,5,6],[3,1,2],[4,2,8],[2,8,15],[6,3,9],[3,6,7],[1,7,8],[1,2,3]] 16

Explanation for Test Case 1

As explained in the example, the shortest path from vertex 1 to vertex 5 is 1→3→51 \rightarrow 3 \rightarrow 5, with a length of 3.

Explanation for Test Case 2

The shortest path from vertex 1 to vertex 8 is 1→2→3→5→81 \rightarrow 2 \rightarrow 3 \rightarrow 5 \rightarrow 8, with a length of 16.