Lesson 36Intermediate56 minAssessment-backed

Shortest Path Basics

Choose shortest-path approaches based on weights, constraints, negative costs, and graph shape.

What you will be able to do

Distinguish unweighted shortest path from weighted shortest path.

Choose BFS, Dijkstra, Bellman-Ford, or DAG shortest path based on constraints.

Implement Dijkstra-style relaxation with a priority queue conceptually.

Explain stale queue entries and distance relaxation.

Connect shortest paths to routing, logistics, latency, recommendations, and risk scoring.

Shortest path is not one algorithm. The right method depends on what an edge means: one hop, distance, time, money, risk, or negative adjustment. The cost model decides the algorithm.

Choose by Edge Cost

If every edge has the same cost, BFS is enough. If weights are non-negative, Dijkstra is the standard baseline. If negative edges exist, Dijkstra is unsafe and you need a different algorithm such as Bellman-Ford, or a domain-specific model.

Shortest path algorithm decision table — The edge-cost rule prevents using the wrong shortest-path algorithm.

Scenario: Delivery Routing

A delivery service routes drivers through roads with travel-time estimates. Fewest turns is not the same as fastest route. Because edge weights are travel times and non-negative, BFS is wrong and Dijkstra-style relaxation is the correct baseline.

Graph condition	Use	Why
Unweighted hops	BFS	Layers equal shortest hop count.
Non-negative weights	Dijkstra	Always expands cheapest known frontier.
Negative weights	Bellman-Ford or re-model	Dijkstra assumption breaks.
DAG with weights	Topological DP	Dependencies give safe order.

Dijkstra relaxation updates distance estimates — Relaxation asks whether this edge improves the best known cost.

Same Pattern in Java, Python, and JavaScript

This Dijkstra baseline returns non-negative shortest distances from a start node.

import java.util.*;

record Edge(String to, int weight) {}
record State(String node, int distance) {}

class DijkstraBasic {
    static Map<String, Integer> shortest(Map<String, List<Edge>> graph, String start) {
        Map<String, Integer> dist = new HashMap<>();
        PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingInt(State::distance));
        dist.put(start, 0);
        pq.offer(new State(start, 0));
        while (!pq.isEmpty()) {
            State state = pq.poll();
            if (state.distance() != dist.get(state.node())) continue;
            for (Edge edge : graph.getOrDefault(state.node(), List.of())) {
                int nextDist = state.distance() + edge.weight();
                if (nextDist < dist.getOrDefault(edge.to(), Integer.MAX_VALUE)) {
                    dist.put(edge.to(), nextDist);
                    pq.offer(new State(edge.to(), nextDist));
                }
            }
        }
        return dist;
    }
}

Assessment trap

Dijkstra assumes non-negative edge weights. If a cost can be negative, saying Dijkstra without qualifying the constraint is an assessment failure.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

Return non-negative shortest distances from one start node.
Given directed weighted times, return how long until all nodes receive a signal.
A graph can contain negative edge weights. Explain why Dijkstra is unsafe and provide a Bellman-Ford style baseline.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Example	Brute-force approach	Stronger solution	Production notes
Delivery route	Use BFS because it is shortest.	Use Dijkstra when roads have non-negative travel times.	Fewest roads is not fastest route.
Network latency	Sort all paths by guessed cost.	Relax edges with a priority queue ordered by current distance.	Skip stale entries after better paths are found.
Discount/rebate graph	Use Dijkstra with negative costs.	Use Bellman-Ford or remodel costs if negative edges exist.	Dijkstra's greedy assumption is invalid with negative weights.

Solved modelInterview Question Solutions

Question 1: Dijkstra Shortest Distances

Return non-negative shortest distances from one start node. Use Dijkstra with a priority queue and relaxation. Skip stale queue records when they no longer match the best known distance.

import java.util.*;

record Edge(String to, int weight) {}
record State(String node, int distance) {}

class DijkstraBasic {
    static Map<String, Integer> shortest(Map<String, List<Edge>> graph, String start) {
        Map<String, Integer> dist = new HashMap<>();
        PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingInt(State::distance));
        dist.put(start, 0);
        pq.offer(new State(start, 0));
        while (!pq.isEmpty()) {
            State state = pq.poll();
            if (state.distance() != dist.get(state.node())) continue;
            for (Edge edge : graph.getOrDefault(state.node(), List.of())) {
                int nextDist = state.distance() + edge.weight();
                if (nextDist < dist.getOrDefault(edge.to(), Integer.MAX_VALUE)) {
                    dist.put(edge.to(), nextDist);
                    pq.offer(new State(edge.to(), nextDist));
                }
            }
        }
        return dist;
    }
}

Question 2: Network Delay Time

Given directed weighted times, return how long until all nodes receive a signal. Run Dijkstra from the source. The answer is the maximum shortest distance if all nodes are reachable; otherwise return -1.

import java.util.*;
record E(int to,int w){} record S(int node,int d){}
class NetworkDelay { static int delay(int[][] times,int n,int k){ Map<Integer,List<E>> g=new HashMap<>(); for(int[] t:times) g.computeIfAbsent(t[0],x->new ArrayList<>()).add(new E(t[1],t[2])); int[] dist=new int[n+1]; Arrays.fill(dist,Integer.MAX_VALUE); dist[k]=0; PriorityQueue<S> pq=new PriorityQueue<>(Comparator.comparingInt(S::d)); pq.offer(new S(k,0)); while(!pq.isEmpty()){ S s=pq.poll(); if(s.d()!=dist[s.node()]) continue; for(E e:g.getOrDefault(s.node(),List.of())) if(s.d()+e.w()<dist[e.to()]){ dist[e.to()]=s.d()+e.w(); pq.offer(new S(e.to(),dist[e.to()])); } } int ans=0; for(int i=1;i<=n;i++){ if(dist[i]==Integer.MAX_VALUE) return -1; ans=Math.max(ans,dist[i]); } return ans; } }

Question 3: Negative Edge Choice

A graph can contain negative edge weights. Explain why Dijkstra is unsafe and provide a Bellman-Ford style baseline. Dijkstra finalizes nodes greedily, which can be invalidated by a later negative edge. Bellman-Ford relaxes every edge repeatedly and can detect negative cycles.

import java.util.*;
class BellmanFord { static long[] shortest(int n, int[][] edges, int start) { long INF = Long.MAX_VALUE / 4; long[] dist = new long[n]; Arrays.fill(dist, INF); dist[start] = 0; for (int i = 0; i < n - 1; i++) for (int[] e : edges) if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2]; return dist; } }

Solved modelWorked Interview Answer

Compute shortest distances from one start node when all edge weights are non-negative. Dijkstra repeatedly expands the cheapest known frontier and relaxes outgoing edges. Stale priority-queue entries are ignored when a better distance was found later.

import java.util.*;

record Edge(String to, int weight) {}
record State(String node, int distance) {}

class DijkstraBasic {
    static Map<String, Integer> shortest(Map<String, List<Edge>> graph, String start) {
        Map<String, Integer> dist = new HashMap<>();
        PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingInt(State::distance));
        dist.put(start, 0);
        pq.offer(new State(start, 0));
        while (!pq.isEmpty()) {
            State state = pq.poll();
            if (state.distance() != dist.get(state.node())) continue;
            for (Edge edge : graph.getOrDefault(state.node(), List.of())) {
                int nextDist = state.distance() + edge.weight();
                if (nextDist < dist.getOrDefault(edge.to(), Integer.MAX_VALUE)) {
                    dist.put(edge.to(), nextDist);
                    pq.offer(new State(edge.to(), nextDist));
                }
            }
        }
        return dist;
    }
}

Hands-on drillTry It Yourself

Practice task

For a graph with edge weights 1, 4, and 10, trace Dijkstra from the start node. Record every distance relaxation.

Failure patternsCommon Mistakes to Avoid

Using BFS on weighted routes.
Using Dijkstra with negative edges.
Treating first discovery as final in weighted graphs.
Not skipping stale priority-queue entries.
Ignoring unreachable nodes.

Execution guardrailQuick-Start Checklist

Identify whether graph is weighted.
Check for negative weights.
Choose BFS, Dijkstra, Bellman-Ford, or DAG DP.
Initialize start distance to 0.
Relax edges.
Handle stale queue entries and unreachable nodes.

Recall drillKnowledge Check

Question	Strong answer
When is BFS enough?	Unweighted or equal-cost edges.
When is Dijkstra valid?	Non-negative edge weights.
What is relaxation?	Updating a neighbor when a cheaper path is found.

VocabularyKey Terms

Term	Meaning
Distance	Best known cost from start.
Relaxation	Improving a distance through an edge.
Priority queue	Frontier ordered by current best distance.
Stale entry	Old queue record worse than current distance.
Negative edge	An edge that reduces path cost.

Next practiceFurther Reading

Practice network delay time, cheapest flights, and shortest path in weighted grids.
Study Bellman-Ford for negative edges.
Review heaps before optimizing Dijkstra.

Depth-First Search

DP Intuition: Overlapping Subproblems