Shortest Path in Weighted Graph

Graph Hard 21 views

Like3

Shortest Path in Weighted Graph is about finding the cheapest route, not the route with the fewest hops. You are given n nodes, weighted undirected edges, a source, and a destination. Return the minimum total weight from source to destination, or -1 if no route exists.

Because edge weights are positive, Dijkstra with a min-heap is the right move. Start with distance 0 at source, always pop the node with the smallest known distance, then relax its neighbors. If going through the current node gives a cheaper distance, update it and push the new state into the heap.

There are two easy-to-miss details. First, build adjacency in both directions since the graph is undirected. Second, skip stale heap entries when their cost is already worse than the best saved distance for that node. That keeps the run efficient and avoids extra reprocessing.

The judge includes disconnected graphs, direct-but-expensive edges versus longer-but-cheaper paths, and empty-edge cases. So keep it simple: one integer output only, with strict relax logic and clean distance tracking. Quick intuition: think like GPS, always expand the currently cheapest checkpoint first.

Also keep in mind that a node may enter the heap multiple times with different costs. That is normal. You only trust the smallest valid one, and ignore the rest. This small rule is what keeps answers correct and performance stable on dense inputs.

Examples

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 - Budibadu

Best Answers

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;
}

Comments (0)

Join the Discussion

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

Shortest Path in Weighted Graph

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Graph Problems

Catalog Shelf Lineup

Ascending Manifest

Memory Rune Sequencer

Starfall Signal Map

Comments (0)

Join the Discussion