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 | # e.g. |

## 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 | INF | 80 | INF | `30` |
90 | INF | |

3 | F | `40` |
70 | INF | 90 | INF | ||

4 | C | `50` |
INF | 90 | 60 | |||

5 | D | INF | 70 | `60` |
||||

6 | H | INF | `70` |
|||||

7 | G | INF |

`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 | function Dijkstra(Graph, source): |

## 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:

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.

## Solution

1 | from collections import defaultdict |