Dijkstra’s AWESOME algorithm 🕶
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.
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.
INF represents Infinity that no edge to that node. Finally, node
E won’t be picked, as it’s unreachable from node
function Dijkstra(Graph, source):
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.
N will be in the range [1, 100].
K will be in the range [1, N].
The length of times will be in the range [1, 6000].
All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.
from collections import defaultdict