Shortest Path in Weighted Graph

Published at05 Jan 2026

Graph Hard 23 views

Like3

You are given a weighted graph with n nodes, a list of edges [u, v, w], and two nodes called source and destination. You need the minimum total weight needed to travel from the source to the destination.

Some routes may use fewer edges but still cost more, so counting hops is not enough. You have to compare the total sum of edge weights along each possible route.

For example, with edges = [[0,1,2],[0,2,4],[1,3,1],[2,3,3],[3,4,5]], the cheapest way from 0 to 4 is 0 -> 1 -> 3 -> 4, which costs 8. If the destination cannot be reached at all, return -1.

So the task is to find the minimum path cost between two nodes in a weighted graph, or report that no path exists.

Example Input & Output

Example 1

Input

n = 5, edges = [[0,1,2], [0,2,4], [1,3,1], [2,3,3], [3,4,5]], source = 0, destination = 4

Output

Explanation

The shortest path is 0 -> 1 -> 3 -> 4, with edge weights 2 + 1 + 5 = 8, which is the minimum total weight to reach node 4 from node 0.

Example 2

Input

n = 2, edges = [], source = 0, destination = 1

Output

-1

Explanation

Since there are no edges in the graph, no path exists between nodes 0 and 1, so the function returns -1.

Example 3

Input

n = 3, edges = [[0,1,1], [1,2,2]], source = 0, destination = 2

Output

Explanation

The shortest path is 0 -> 1 -> 2, with edge weights 1 + 2 = 3, representing the minimum total weight to reach node 2 from node 0.

Algorithm Flow

Recommendation Algorithm Flow for Shortest Path in Weighted Graph

Solution Approach

The standard solution is Dijkstra's algorithm.

First build an adjacency list so you can quickly see which neighbors each node connects to and what each move costs. Then keep a distance array where dist[x] is the best cost found so far for node x.

Use a min-heap priority queue starting from source with distance 0. Each time you pop the node with the smallest current distance, try relaxing all of its outgoing edges. If going through that node gives a neighbor a smaller distance, update it and push the new value into the heap.

When destination is popped, its distance is the shortest possible. If it is never reached, return -1. This runs in about O((n + m) log n) time for m edges.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java


class Solution {
    public int shortest_path(Object nObj, Object edgesObj, Object srcObj, Object dstObj) {
        int n = (int) nObj;
        int source = (int) srcObj;
        int destination = (int) dstObj;
        int[][] edges = (int[][]) edgesObj;
        
        java.util.List<java.util.List<int[]>> adj = new java.util.ArrayList<>();
        for(int i=0; i<n; i++) adj.add(new java.util.ArrayList<>());
        
        for(int[] edge : edges) {
            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
            adj.get(edge[1]).add(new int[]{edge[0], edge[2]});
        }
        
        int[] dist = new int[n];
        java.util.Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;
        
        java.util.PriorityQueue<int[]> pq = new java.util.PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, source});
        
        while(!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0];
            int u = curr[1];
            
            if(u == destination) return d;
            if(d > dist[u]) continue;
            
            for(int[] neighbor : adj.get(u)) {
                int v = neighbor[0];
                int w = neighbor[1];
                if(dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        return -1;
    }
}

javascript

function shortest_path(n, edges, source, destination) {
    const adj = new Map();
    for (const [u, v, w] of edges) {
        if (!adj.has(u)) adj.set(u, []);
        if (!adj.has(v)) adj.set(v, []);
        adj.get(u).push([v, w]);
        adj.get(v).push([u, w]);
    }

    const dist = new Array(n).fill(Infinity);
    dist[source] = 0;
    const pq = [[0, source]];

    while (pq.length > 0) {
        pq.sort((a, b) => a[0] - b[0]);
        const [d, u] = pq.shift();

        if (u === destination) return d;
        if (d > dist[u]) continue;

        const neighbors = adj.get(u) || [];
        for (const [v, w] of neighbors) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push([dist[v], v]);
            }
        }
    }
    return -1;
}

php

<?php
function shortest_path($n, $edges, $source, $destination) {
    $adj = [];
    foreach ($edges as $edge) {
        $adj[$edge[0]][] = [$edge[1], $edge[2]];
        $adj[$edge[1]][] = [$edge[0], $edge[2]];
    }
    
    $dist = array_fill(0, $n, PHP_INT_MAX);
    $dist[$source] = 0;
    $pq = new SplPriorityQueue();
    $pq->insert($source, 0);
    
    while (!$pq->isEmpty()) {
        $u = $pq->extract();
        if ($u == $destination) return $dist[$u];
        
        if (isset($adj[$u])) {
            foreach ($adj[$u] as $neighbor) {
                list($v, $weight) = $neighbor;
                if ($dist[$u] + $weight < $dist[$v]) {
                    $dist[$v] = $dist[$u] + $weight;
                    $pq->insert($v, -$dist[$v]);
                }
            }
        }
    }
    return -1;
}

python

import heapq
from typing import List

def shortest_path(n: int, edges: List[List[int]], source: int, destination: int) -> int:
    adj = {i: [] for i in range(n)}
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))
    
    pq = [(0, source)]
    dist = {i: float('inf') for i in range(n)}
    dist[source] = 0
    
    while pq:
        d, u = heapq.heappop(pq)
        if u == destination:
            return d
        if d > dist[u]:
            continue
        
        for v, weight in adj[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))
                
    return -1

rust

use std::collections::{HashMap, BinaryHeap};
use std::cmp::Reverse;

fn shortest_path(n: i32, edges: Vec<Vec<i32>>, source: i32, destination: i32) -> i32 {
    let mut adj: HashMap<i32, Vec<(i32, i32)>> = HashMap::new();
    for edge in edges {
        adj.entry(edge[0]).or_default().push((edge[1], edge[2]));
        adj.entry(edge[1]).or_default().push((edge[0], edge[2]));
    }

    let mut dist = HashMap::new();
    let mut pq = BinaryHeap::new();

    dist.insert(source, 0);
    pq.push(Reverse((0, source)));

    while let Some(Reverse((d, u))) = pq.pop() {
        if u == destination { return d; }
        if d > *dist.get(&u).unwrap_or(&std::i32::MAX) { continue; }

        if let Some(neighbors) = adj.get(&u) {
            for &(v, weight) in neighbors {
                let new_dist = d + weight;
                if new_dist < *dist.get(&v).unwrap_or(&std::i32::MAX) {
                    dist.insert(v, new_dist);
                    pq.push(Reverse((new_dist, v)));
                }
            }
        }
    }
    -1
}

typescript

function shortest_path(n: number, edges: number[][], source: number, destination: number): number {
    const adj: { [key: number]: number[][] } = {};
    
    // Explicit loop for edges to avoid destructuring if strictly ES3/ES5
    for (var i = 0; i < edges.length; i++) {
        var u = edges[i][0];
        var v = edges[i][1];
        var w = edges[i][2];
        
        if (!adj[u]) adj[u] = [];
        if (!adj[v]) adj[v] = [];
        adj[u].push([v, w]);
        adj[v].push([u, w]);
    }

    // Manual Array fill
    var dist = new Array(n);
    for(var i=0; i<n; i++) dist[i] = Number.MAX_VALUE;
    
    dist[source] = 0;
    
    // Simple priority queue using array
    var pq: number[][] = []; 
    pq.push([0, source]);

    while (pq.length > 0) {
        // Sort descending to pop from end (efficient pop)
        pq.sort(function(a, b) { return b[0] - a[0]; });
        var popped = pq.pop();
        if (!popped) break;
        
        var d = popped[0];
        var u = popped[1];

        if (u === destination) return d;
        if (d > dist[u]) continue;

        var neighbors = adj[u] || [];
        for (var j = 0; j < neighbors.length; j++) {
            var v = neighbors[j][0];
            var w = neighbors[j][1];
            
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push([dist[v], v]);
            }
        }
    }
    return -1;
}

Related Graph Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Shortest Path in Weighted Graph

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Graph Challenges

Catalog Shelf Lineup

Ascending Manifest

Memory Rune Sequencer

Starfall Signal Map

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.