Learn
Exam

Dijkstra Shortest Path Tracking 1

Difficulty
INTERMEDIATE

Problem

Given a directed graph represented as an adjacency matrix, write a solution function that returns the shortest path from vertex 1 to vertex n. The shortest path should include both the starting vertex 1 and the destination vertex n in the result.

Concept Explanation

Dijkstra's Algorithm is a one-to-all shortest path algorithm that can be applied to directed graphs where all edge weights are positive.
To calculate the shortest path, we update the Dist array and simultaneously save the traversed path whenever we update Dist. After Dijkstra's algorithm completes, the path is backtracked from the destination to retrieve the shortest path.

Reference: Dijkstra's Algorithm

Assume the following directed graph is given.

Starting from the initial vertex, we initialize both the Dist array and the Path array.

During Dijkstra's algorithm, if Dist is updated, the path information (vertices and edges) used for the update is stored in Path.

The Dijkstra process continues with the priority queue as usual.

After completing Dijkstra's algorithm, we have the Dist and Path information as shown below.

To find the shortest path from vertex 1 to vertex 5, we backtrack starting from the destination vertex 5 using the stored path information in Path.

This backtracking continues until reaching the start vertex.

Based on this path-tracking algorithm, we can determine that the shortest path from vertex 1 to vertex 5 is 1→3→51 \rightarrow 3 \rightarrow 5.

Constraints

  • The number of vertices n is a natural number between 2 and 2,000 inclusive.
  • The parameter adjMat is a 2D array representing the adjacency matrix of a directed graph.
    • adjMat[i][j] represents the weight of the edge from vertex i to vertex j.
    • adjMat[i][j] is an integer between 0 and 20,000 inclusive.
    • If adjMat[i][j] is 0, it means that there is no edge from vertex i to vertex j.
  • There is always exactly one shortest path from vertex 1 to vertex n based on the given edge information.

Test Case

Test Case Number adjMat return
1 [[0,3,2,0,10],[0,0,0,1,0],[0,0,0,4,1],[0,0,0,0,3],[0,0,0,0,0]] [1,3,5]
2 [[0,0,4,0,0],[0,0,0,0,0],[0,0,0,8,0],[0,10,0,0,5],[0,6,0,0,0]] [1,3,4,5]
3 [[0,0,10,1,0,0],[6,0,7,2,6,0],[6,1,0,6,5,1],[8,6,10,0,6,5],[0,3,1,0,0,4],[0,4,3,4,0,0]] [1,4,6]

Explanation for Test Case 1

  • Example 1 matches the example in the problem description. The shortest path is 1→3→51 \rightarrow 3 \rightarrow 5, with a total path length of 3.

Explanation for Test Case 2

  • The only shortest path from vertex 1 to vertex 5 is 1→3→4→51 \rightarrow 3 \rightarrow 4 \rightarrow 5, with a total path length of 17.

Explanation for Test Case 3

  • The shortest path from vertex 1 to vertex 6 is 1→4→61 \rightarrow 4 \rightarrow 6, with a total path length of 6.