Graph Breadth First Search Depth First Search Shortest Path Minimum Spanning Tree
Proficient Level

Implement the dijkstraShortestPathSimple method that returns the shortest weighted path using Dijkstra-style logic.

The input represents a weighted graph. nodes is the number of vertices, each edge is given as [from, to, weight], and source and target identify the required path.

Your task is to return the shortest distance from source to target. If the target cannot be reached, return -1.

For example, from node 0 to node 1, the path 0 -> 2 -> 1 with weights 1 + 2 is shorter than the direct edge with weight 4, so the answer is 3.

Example 1
Input:
nodes (int) = 3
edges (int[][]) = [[0,1,4],[0,2,1],[2,1,2]]
size (int) = 3
source (int) = 0
target (int) = 1
Return:
(int) 3
Example 2
Input:
nodes (int) = 3
edges (int[][]) = [[0,1,1],[1,2,2],[0,2,5]]
size (int) = 3
source (int) = 0
target (int) = 2
Return:
(int) 3
Example 3
Input:
nodes (int) = 2
edges (int[][]) = []
size (int) = 0
source (int) = 0
target (int) = 1
Return:
(int) -1

Use Dijkstra algorithm because the edges have weights.

Keep the best known distance for each node. Start with distance 0 for the source and infinity for all others. Repeatedly choose the unvisited node with the smallest distance and relax its outgoing edges.

When the target node gets its final shortest distance, return it. If it remains unreachable, return -1.

Pseudocode:

function dijkstraShortestPathSimple(nodes, edges, size, source, target):
    graph = create weighted adjacency list
    for each edge [u, v, weight] in edges:
        add [v, weight] to graph[u]
    distance = array filled with infinity
    visited = array filled with false
    distance[source] = 0
    repeat nodes times:
        current = unvisited node with smallest distance
        if current does not exist:
            break
        visited[current] = true
        for each [nextNode, weight] in graph[current]:
            if distance[current] + weight < distance[nextNode]:
                distance[nextNode] = distance[current] + weight
    if distance[target] is infinity:
        return -1
    return distance[target]
Run your code to see the result.