0743_network_delay_time.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>LC 743: Network Delay Time - Algorithm Visualization</title>
    <link rel="stylesheet" href="styles.css">
    <script src="https://d3js.org/d3.v7.min.js"></script>
</head>
<body>
    <div class="container">
        <div class="problem-info">
            <h1><span class="problem-number">#743</span> Network Delay Time</h1>
            <p>Given a network of n nodes and weighted edges, find the time for a signal to reach all nodes from source k. Return -1 if impossible.</p>
            <div class="problem-meta">
                <span class="meta-tag">📊 Graph</span>
                <span class="meta-tag">🔍 Dijkstra</span>
                <span class="meta-tag">⏱️ O(E log V)</span>
                <span class="meta-tag">💾 O(V + E)</span>
            </div>
            <div class="file-ref">
                📄 Python: <code>python/0743_network_delay_time/0743_network_delay_time.py</code>
            </div>
            </div>

        <div class="explanation-panel">
            <h4>🧠 How It Works (Layman's Terms)</h4>
            <p>Use <strong>Dijkstra's algorithm</strong> to find shortest paths from source to all nodes:</p>
            <ul>
                <li><strong>Min-Heap:</strong> Always process the node with smallest known distance</li>
                <li><strong>Relaxation:</strong> Update neighbors if we found a shorter path</li>
                <li><strong>Answer:</strong> Maximum distance among all reachable nodes</li>
                <li><strong>Unreachable:</strong> If any node has ∞ distance, return -1</li>
            </ul>
        </div>


        <div class="visualization-section">
            <h3>🎬 Step-by-Step Visualization</h3>
            
            <div class="controls">
                <button class="btn btn-primary" id="startBtn" onclick="start()">▶ Start</button>
                <button class="btn" onclick="stepForward()">Step →</button>
                <button class="btn btn-warning" onclick="reset()">Reset</button>
            </div>

            <div class="status-message" id="statusMessage">
                Click Start to begin Dijkstra's algorithm from node 1
            </div>

            <div style="display: flex; gap: 20px; flex-wrap: wrap; margin-top: 20px;">
                <div style="flex: 2; min-width: 400px;">
                    <svg id="graphViz" width="100%" height="400"></svg>
                </div>
                <div style="flex: 1; min-width: 200px;">
                    <h4>📊 Distance Table</h4>
                    <div id="distTable" style="padding: 15px; background: #f5f5f5; border-radius: 12px; margin-bottom: 15px;"></div>
                    
                    <h4>⏱️ Min-Heap (Priority Queue)</h4>
                    <div id="heapDisplay" style="padding: 15px; background: #e3f2fd; border-radius: 12px; margin-bottom: 15px; font-family: monospace;"></div>
                    
                    <h4>✅ Visited Nodes</h4>
                    <div id="visitedDisplay" style="padding: 15px; background: #e8f5e9; border-radius: 12px;"></div>
                </div>
            </div>

            <div id="answerBox" style="margin-top: 20px; padding: 20px; background: linear-gradient(135deg, #667eea, #764ba2); color: white; border-radius: 12px; text-align: center; font-size: 1.3em; display: none;">
                Network Delay Time: <span id="answer" style="font-weight: bold; font-size: 1.5em;">0</span>
            </div>
        </div>

        <div class="code-section">
            <h3>💻 Python Solution (Dijkstra)</h3>
            <div class="code-block">
                <pre>import heapq
import collections
from math import inf


"""
LeetCode Network Delay Time

Problem from LeetCode: https://leetcode.com/problems/network-delay-time/

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges 
times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to 
travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. 
If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Example 2:
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Example 3:
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Constraints:
- 1 &lt;= k &lt;= n &lt;= 100
- 1 &lt;= times.length &lt;= 6000
- times[i].length == 3
- 1 &lt;= ui, vi &lt;= n
- ui != vi
- 0 &lt;= wi &lt;= 100
- All the pairs (ui, vi) are unique (i.e., no multiple edges).
"""

class Solution:

    def network_delay_time(self, times: list[list[int]], n: int, k: int) -&gt;int:
        graph = collections.defaultdict(list)
        for source, target, time in times:
            graph[source].append((target, time))
        pq = [(0, k)]
        distances = [inf] * (n + 1)
        distances[k] = 0
        distances[0] = 0
        while pq:
            current_dist, current_node = heapq.heappop(pq)
            if current_dist &gt; distances[current_node]:
                continue
            for next_node, edge_time in graph[current_node]:
                next_dist = current_dist + edge_time
                if next_dist &lt; distances[next_node]:
                    distances[next_node] = next_dist
                    heapq.heappush(pq, (next_dist, next_node))
        max_dist = max(distances[1:])
        return max_dist if max_dist &lt; inf else -1


if __name__ == '__main__':
    # Example usage based on LeetCode sample
    solution = Solution()
    
    # Example 1
    times = [[2,1,1],[2,3,1],[3,4,1]]
    n = 4
    k = 2
    result = solution.network_delay_time(times, n, k)
    print(f"Example 1: {result}")  # Expected: 2
    
    # Example 2
    times = [[1,2,1]]
    n = 2
    k = 1
    result = solution.network_delay_time(times, n, k)
    print(f"Example 2: {result}")  # Expected: 1
    
    # Example 3
    times = [[1,2,1]]
    n = 2
    k = 2
    result = solution.network_delay_time(times, n, k)
    print(f"Example 3: {result}")  # Expected: -1
</pre>
            </div>
        </div>
    </div>

    <script>
        // Graph data: [u, v, weight]
        const times = [
            [1, 2, 1], [1, 3, 4], [2, 3, 2], [2, 4, 6], 
            [3, 4, 3], [3, 5, 5], [4, 5, 1]
        ];
        const n = 5;
        const source = 1;

        let nodes = [];
        let dist = {};
        let heap = [];
        let visited = new Set();
        let currentNode = null;
        let isRunning = false;
        let stepIndex = 0;
        let steps = [];

        function buildGraph() {
            const graph = {};
            for (let i = 1; i <= n; i++) graph[i] = [];
            for (const [u, v, w] of times) {
                graph[u].push([v, w]);
            }
            return graph;
        }

        function precomputeSteps() {
            const graph = buildGraph();
            const localDist = {};
            for (let i = 1; i <= n; i++) localDist[i] = Infinity;
            localDist[source] = 0;
            
            const localHeap = [[0, source]];
            const localVisited = new Set();
            steps = [];
            
            steps.push({
                type: 'init',
                dist: {...localDist},
                heap: [...localHeap],
                visited: new Set(localVisited),
                message: `Initialize: Set dist[${source}] = 0, push (0, ${source}) to heap`
            });

            while (localHeap.length > 0) {
                localHeap.sort((a, b) => a[0] - b[0]);
                const [d, node] = localHeap.shift();
                
                if (localVisited.has(node)) continue;
                localVisited.add(node);
                
                steps.push({
                    type: 'visit',
                    node,
                    dist: {...localDist},
                    heap: [...localHeap],
                    visited: new Set(localVisited),
                    message: `Visit node ${node} (distance = ${d})`
                });

                for (const [neighbor, weight] of graph[node]) {
                    const newDist = localDist[node] + weight;
                    if (newDist < localDist[neighbor]) {
                        localDist[neighbor] = newDist;
                        localHeap.push([newDist, neighbor]);
                        steps.push({
                            type: 'relax',
                            from: node,
                            to: neighbor,
                            newDist,
                            dist: {...localDist},
                            heap: [...localHeap],
                            visited: new Set(localVisited),
                            message: `Relax: dist[${neighbor}] = ${newDist} (via node ${node})`
                        });
                    }
                }
            }

            const maxDist = Math.max(...Object.values(localDist));
            steps.push({
                type: 'done',
                dist: {...localDist},
                heap: [],
                visited: new Set(localVisited),
                answer: maxDist === Infinity ? -1 : maxDist,
                message: `Done! Network delay time = ${maxDist === Infinity ? -1 : maxDist}`
            });
        }

        function initPositions() {
            const positions = [
                { id: 1, x: 100, y: 200 },
                { id: 2, x: 250, y: 100 },
                { id: 3, x: 250, y: 300 },
                { id: 4, x: 400, y: 100 },
                { id: 5, x: 400, y: 300 }
            ];
            nodes = positions;
        }

        function render() {
            const svg = d3.select("#graphViz");
            svg.selectAll("*").remove();

            const container = svg.node().parentElement;
            const width = container.clientWidth;
            const height = 400;
            svg.attr("viewBox", `0 0 ${width} ${height}`);

            const g = svg.append("g").attr("transform", `translate(${(width - 500) / 2}, 0)`);

            // Define arrow marker
            g.append("defs").append("marker")
                .attr("id", "arrow")
                .attr("viewBox", "0 -5 10 10")
                .attr("refX", 35)
                .attr("refY", 0)
                .attr("markerWidth", 6)
                .attr("markerHeight", 6)
                .attr("orient", "auto")
                .append("path")
                .attr("d", "M0,-5L10,0L0,5")
                .attr("fill", "#999");

            // Draw edges
            times.forEach(([u, v, w]) => {
                const from = nodes.find(n => n.id === u);
                const to = nodes.find(n => n.id === v);
                const dx = to.x - from.x;
                const dy = to.y - from.y;
                const midX = (from.x + to.x) / 2;
                const midY = (from.y + to.y) / 2;

                g.append("line")
                    .attr("x1", from.x).attr("y1", from.y)
                    .attr("x2", to.x).attr("y2", to.y)
                    .attr("stroke", "#ccc").attr("stroke-width", 2)
                    .attr("marker-end", "url(#arrow)");

                g.append("rect")
                    .attr("x", midX - 12).attr("y", midY - 10)
                    .attr("width", 24).attr("height", 20)
                    .attr("fill", "#fff").attr("rx", 4);

                g.append("text")
                    .attr("x", midX).attr("y", midY + 5)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "12px").attr("fill", "#666")
                    .text(w);
            });

            // Draw nodes
            nodes.forEach(node => {
                const isSource = node.id === source;
                const isVisited = visited.has(node.id);
                const isCurrent = currentNode === node.id;
                
                let fill = "#667eea";
                if (isSource) fill = "#ff9800";
                if (isVisited) fill = "#4caf50";
                if (isCurrent) fill = "#e91e63";

                g.append("circle")
                    .attr("cx", node.x).attr("cy", node.y).attr("r", 25)
                    .attr("fill", fill)
                    .attr("stroke", isCurrent ? "#c2185b" : "#5a6fd6")
                    .attr("stroke-width", isCurrent ? 4 : 2);

                g.append("text")
                    .attr("x", node.x).attr("y", node.y + 6)
                    .attr("text-anchor", "middle")
                    .attr("fill", "white").attr("font-weight", "bold").attr("font-size", "16px")
                    .text(node.id);

                // Distance label
                const d = dist[node.id];
                const distLabel = d === undefined ? "∞" : (d === Infinity ? "∞" : d);
                g.append("text")
                    .attr("x", node.x).attr("y", node.y - 35)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "12px")
                    .attr("fill", d === 0 ? "#ff9800" : "#333")
                    .text(`d=${distLabel}`);
            });

            // Legend
            const legend = svg.append("g").attr("transform", "translate(10, 360)");
            const items = [
                { color: "#ff9800", label: "Source" },
                { color: "#e91e63", label: "Current" },
                { color: "#4caf50", label: "Visited" },
                { color: "#667eea", label: "Unvisited" }
            ];
            items.forEach((item, i) => {
                legend.append("circle")
                    .attr("cx", i * 100).attr("cy", 0).attr("r", 8)
                    .attr("fill", item.color);
                legend.append("text")
                    .attr("x", i * 100 + 15).attr("y", 5)
                    .attr("font-size", "11px")
                    .text(item.label);
            });

            // Update side panels
            updateDistTable();
            updateHeapDisplay();
            updateVisitedDisplay();
        }

        function updateDistTable() {
            const container = document.getElementById('distTable');
            let html = '<table style="width: 100%; font-size: 0.9em;">';
            html += '<tr><th>Node</th><th>Distance</th></tr>';
            for (let i = 1; i <= n; i++) {
                const d = dist[i];
                const val = d === undefined ? "∞" : (d === Infinity ? "∞" : d);
                const bg = visited.has(i) ? "#c8e6c9" : (currentNode === i ? "#f8bbd9" : "");
                html += `<tr style="background: ${bg}"><td>${i}</td><td>${val}</td></tr>`;
            }
            html += '</table>';
            container.innerHTML = html;
        }

        function updateHeapDisplay() {
            const container = document.getElementById('heapDisplay');
            if (heap.length === 0) {
                container.textContent = '(empty)';
                return;
            }
            container.innerHTML = heap.map(([d, node]) => 
                `<span style="background: #bbdefb; padding: 3px 8px; margin: 2px; border-radius: 4px; display: inline-block;">(${d}, ${node})</span>`
            ).join(' ');
        }

        function updateVisitedDisplay() {
            const container = document.getElementById('visitedDisplay');
            if (visited.size === 0) {
                container.textContent = '(none)';
                return;
            }
            container.innerHTML = Array.from(visited).sort().map(v => 
                `<span style="background: #a5d6a7; padding: 5px 12px; margin: 3px; border-radius: 15px; display: inline-block;">${v}</span>`
            ).join(' ');
        }

        function stepForward() {
            if (stepIndex >= steps.length) return;
            
            const step = steps[stepIndex];
            dist = step.dist;
            heap = step.heap;
            visited = step.visited;
            currentNode = step.node || null;
            
            document.getElementById('statusMessage').textContent = step.message;
            
            if (step.type === 'done') {
                document.getElementById('answerBox').style.display = 'block';
                document.getElementById('answer').textContent = step.answer;
                document.getElementById('startBtn').textContent = '▶ Start';
                isRunning = false;
            }
            
            stepIndex++;
            render();
        }

        async function start() {
            if (isRunning) {
                isRunning = false;
                document.getElementById('startBtn').textContent = '▶ Start';
                return;
            }
            
            isRunning = true;
            document.getElementById('startBtn').textContent = '⏸ Pause';
            
            while (stepIndex < steps.length && isRunning) {
                stepForward();
                await new Promise(r => setTimeout(r, 800));
            }
            
            if (!isRunning) return;
            document.getElementById('startBtn').textContent = '▶ Start';
            isRunning = false;
        }

        function reset() {
            isRunning = false;
            stepIndex = 0;
            dist = {};
            for (let i = 1; i <= n; i++) dist[i] = i === source ? 0 : Infinity;
            heap = [[0, source]];
            visited = new Set();
            currentNode = null;
            
            document.getElementById('statusMessage').textContent = 'Click Start to begin Dijkstra\'s algorithm from node 1';
            document.getElementById('answerBox').style.display = 'none';
            document.getElementById('startBtn').textContent = '▶ Start';
            
            precomputeSteps();
            render();
        }

        initPositions();
        reset();
        window.addEventListener('resize', render);
    </script>
</body>
</html>