743. Network Delay Time (Naive Dijkstra)¶

Edited by Charles

Medium · Python · Graph

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Use Dijkstra's Algorithm to find the shortest distance from the starting node k to every other node.

Original study notes follow, including intermediate snippets and earlier attempts.

Idea¶

Use Dijkstra's Algorithm to find the shortest distance from the starting node k to every other node.

This version uses:

Adjacency Matrix
Linear Scan
Visited Array

It is the naive Dijkstra implementation without a min-heap.

The problem asks how long it takes for the signal to reach all nodes.

So after finding the shortest distance from k to every node, the answer is:

max(minDist[1:])

because the total delay is determined by the node that receives the signal last.

If any node is unreachable, return -1.

Graph Representation¶

Each edge:

[u, v, w]

means:

u --w--> v

We use an adjacency matrix:

graph = [[float('inf')] * (n + 1) for _ in range(n + 1)]

Then:

for u, v, w in times:
    graph[u][v] = w

So:

graph[u][v]

represents the travel time from node u to node v.

If:

graph[u][v] == float('inf')

then there is no direct edge from u to v.

`minDist`¶

Define:

minDist[i]

as:

The shortest distance currently known from the starting node k to node i.

Initially:

minDist = [float('inf')] * (n + 1)
minDist[k] = 0

The starting node has distance 0 from itself.

All other nodes are initially unreachable, so their distances are set to infinity.

Example:

k = 2

node:       1    2    3    4
minDist:   inf   0   inf  inf

`visit`¶

Define:

visit[i]

as:

Whether the shortest distance to node i has already been finalized.

Initially:

visit = [False] * (n + 1)

When:

visit[i] = True

it means the shortest distance from k to node i has been determined and will no longer change.

Step 1: Find the Closest Unvisited Node¶

At each round, find the unvisited node with the smallest current distance:

minVal = float('inf')
cur = -1

for node in range(1, n + 1):
    if not visit[node] and minDist[node] < minVal:
        minVal = minDist[node]
        cur = node

This is the key step of naive Dijkstra.

Among all unvisited nodes, choose the one with the smallest:

minDist[node]

Then:

cur

is the next node whose shortest distance can be finalized.

Why Can We Finalize `cur`?¶

Dijkstra assumes all edge weights are non-negative.

If cur currently has the smallest distance among all unvisited nodes, no other unvisited path can later produce a shorter route to cur.

Therefore:

visit[cur] = True

and:

minDist[cur]

is now finalized.

Why `cur == -1`?¶

We initialize:

cur = -1

and only update it when:

minDist[node] < minVal

Since:

minVal = float('inf')

a node whose distance is also inf will not be selected because:

inf < inf

is False.

Therefore, if:

cur == -1

after scanning all nodes, it means every remaining unvisited node has:

minDist[node] == float('inf')

In other words:

No remaining node is reachable from the starting node.

So we can stop early:

if cur == -1:
    break

Step 2: Relax the Neighbors¶

After finalizing cur, try to update all nodes directly reachable from cur.

Suppose:

k → ... → cur → node

We already know:

minDist[cur]

and the edge:

graph[cur][node]

Then the new possible distance to node is:

minDist[cur] + graph[cur][node]

If this is smaller than the current:

minDist[node]

we update it.

In the code:

if (
    not visit[node]
    and graph[cur][node] != float('inf')
    and graph[cur][node] + minDist[cur] < minDist[node]
):
    minDist[node] = graph[cur][node] + minDist[cur]

This process is called relaxation.

Relaxation Formula¶

The core transition is:

minDist[node] = min(
    minDist[node],
    minDist[cur] + graph[cur][node]
)

It compares two possibilities:

Keep the previously known shortest distance.
Reach node through cur.

If going through cur is shorter, update the distance.

Hand Simulation¶

Suppose:

times = [
    [2, 1, 1],
    [2, 3, 1],
    [3, 4, 1]
]

n = 4
k = 2

The graph is:

    1
    ↑
    1
    |
    2 --1--> 3 --1--> 4

Initially:

node:       1     2     3     4
minDist:   inf    0    inf   inf
visit:      F     F     F     F

Round 1¶

The closest unvisited node is:

cur = 2

because:

minDist[2] = 0

Mark it visited:

visit[2] = True

Relax its neighbors.

For:

2 → 1

we get:

0 + 1 = 1

so:

minDist[1] = 1

For:

2 → 3

we get:

0 + 1 = 1

so:

minDist[3] = 1

Now:

node:       1    2    3    4
minDist:    1    0    1   inf
visit:      F    T    F    F

Round 2¶

Among unvisited nodes:

1 → distance 1
3 → distance 1
4 → distance inf

The scan finds node 1 first:

cur = 1

Mark:

visit[1] = True

Node 1 has no outgoing edges, so nothing changes.

Round 3¶

The closest remaining node is:

cur = 3

Mark:

visit[3] = True

There is an edge:

3 --1--> 4

So:

minDist[4]
= min(inf, minDist[3] + 1)
= min(inf, 1 + 1)
= 2

Now:

node:       1    2    3    4
minDist:    1    0    1    2
visit:      T    T    T    F

Round 4¶

The last node is:

cur = 4

After processing it:

minDist = [1, 0, 1, 2]

excluding index 0.

Final Answer¶

The signal reaches each node after:

node 1: 1
node 2: 0
node 3: 1
node 4: 2

The last node receives the signal after:

max(minDist[1:])

which is:

So the answer is:

Why Take the Maximum?¶

Dijkstra gives us the shortest distance from k to every node.

But the problem asks:

How long until every node receives the signal?

All nodes have received the signal only when the slowest node receives it.

Therefore:

res = max(minDist[1:])

Unreachable Nodes¶

If one node cannot be reached from k, its distance remains:

float('inf')

Therefore:

res = max(minDist[1:])

will also be:

float('inf')

So:

return -1 if res == float('inf') else res

Key Idea of Naive Dijkstra¶

Each round performs two operations:

Find¶

Find the closest unvisited node:

Unvisited nodes
        ↓
smallest minDist
        ↓
       cur

Relax¶

Use cur to update its neighbors:

minDist[node]
    =
min(
    old distance,
    minDist[cur] + edge weight
)

Then repeat.

Memory:

Find the closest unvisited node → finalize it → relax its neighbors → repeat.

Complexity¶

The outer loop runs at most n times.

Each time, we scan all n nodes to find the closest unvisited node:

O(n)

Then we scan all n nodes again to relax neighbors:

O(n)

Therefore:

Time: O(n²)

The adjacency matrix requires:

Space: O(n²)

So overall:

Time: O(n²)
Space: O(n²)

Code¶

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        minDist = [float('inf')] * (n + 1)
        visit = [False] * (n + 1)
        minDist[k] = 0

        graph = [[float('inf')] * (n + 1) for _ in range(n + 1)]

        for u, v, w in times:
            graph[u][v] = w

        for _ in range(n):
            minVal = float('inf')
            cur = -1

            for node in range(1, n + 1):
                if not visit[node] and minDist[node] < minVal:
                    minVal = minDist[node]
                    cur = node

            if cur == -1:
                break

            visit[cur] = True

            for node in range(1, n + 1):
                if (
                    not visit[node]
                    and graph[cur][node] != float('inf')
                    and graph[cur][node] + minDist[cur] < minDist[node]
                ):
                    minDist[node] = graph[cur][node] + minDist[cur]

        res = max(minDist[1:])

        return -1 if res == float('inf') else res

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	August 28, 2026

Python solution¶

# Deque
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = defaultdict(list)
        for u,v,w in times:
            graph[u].append((v,w))

        distance = [inf] * (n+1)
        distance[k] = 0
        # visited = [k]
        in_queue = [False] * (n+1)
        in_queue[k] = True


        queue = deque()
        queue.append(k)
        while queue:
            cur = queue.popleft()
            in_queue[cur] = False
            for nxt,w in graph[cur]:
                if distance[cur] + w < distance[nxt]:
                    distance[nxt] = distance[cur] + w
                    if not in_queue[nxt]:
                        queue.append(nxt)
                        in_queue[nxt] = True
        ans = max(distance[1:])
        return ans if ans < inf else -1

Back to Day 51 Graph IX · All Algorithm notes

743. Network Delay Time (Naive Dijkstra)¶

Idea¶

Graph Representation¶

minDist¶

visit¶

Step 1: Find the Closest Unvisited Node¶

Why Can We Finalize cur?¶

Why cur == -1?¶

Step 2: Relax the Neighbors¶

Relaxation Formula¶

Hand Simulation¶

Round 1¶

Round 2¶

Round 3¶

Round 4¶

Final Answer¶

Why Take the Maximum?¶

Unreachable Nodes¶

Key Idea of Naive Dijkstra¶

Find¶

Relax¶

Complexity¶

Code¶

Python solution¶

`minDist`¶

`visit`¶

Why Can We Finalize `cur`?¶

Why `cur == -1`?¶