Dijkstra's Algorithm

Dijkstra’s AWESOME algorithm 🕶

Before the Start

We should use a data structure to describe the graph. The graph is a list of edges like (u, v, w), where u is the source vertex, v is the target vertex, and w is the weight.

1
2
3
4
5
6
# e.g.
# raw = [[2,1,1],[2,3,1],[3,4,1]]
# graph = {2: {1: 1, 3: 1}, 3: {4: 1}}
graph = collections.defaultdict(dict)
for u, v, w in raw:
graph[u][v] = w

Introduction

Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph.

As shown above, for example, we pick A as the source.

Round Pick B C D E F G H
1 A 20 INF 80 INF INF 90 INF
2 B 20 INF 80 INF 30 90 INF
3 F 20 40 70 INF 30 90 INF
4 C 20 40 50 INF 30 90 60
5 D 20 40 50 INF 30 70 60
6 H 20 40 50 INF 30 70 60
7 G 20 40 50 INF 30 70 60

INF represents Infinity that no edge to that node. Finally, node E won’t be picked, as it’s unreachable from node A.

Pseudocode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function Dijkstra(Graph, source):

create vertex set Q

for each vertex v in Graph: // Initialization
dist[v] = INFINITY // Unknown distance from source to v
add v to Q // All nodes initially in Q (unvisited nodes)

dist[source] = 0 // Distance from source to source
while Q is not empty:
u = vertex in Q with min dist[u] // Node with the least distance
// will be selected first
remove u from Q

for each neighbor v of u: // where v is still in Q.
alt = dist[u] + length(u, v)
if alt < dist[v]: // A shorter path to v has been found
dist[v] = alt

return dist[]

Problem

Network Delay Time

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Note:

  1. N will be in the range [1, 100].

  2. K will be in the range [1, N].

  3. The length of times will be in the range [1, 6000].

  4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from collections import defaultdict
class Solution(object):
def networkDelayTime(self, times, N, K):
graph = defaultdict(dict)
Q = set(range(N))
for u, v, w in times:
graph[u - 1][v - 1] = w
dist = [float('inf')] * N
dist[K - 1] = 0
while len(Q):
u = None
for vertex in Q:
if u == None or dist[vertex] < dist[u]:
u = vertex
Q.remove(u)
for v in graph[u]:
dist[v] = min(dist[u] + graph[u][v], dist[v])
d = max(dist)
return -1 if d == float('inf') else d
0%