Graphs 0/61

Dijkstra and shortest paths · 2 of 4

Dijkstra

Find the distances from one source when no weight is negative by settling the closest vertex with a min-heap, and adapt the method to another measure of a path, to extra state and to counting shortest paths.

3,523 words · 16 min read

Part 1 of 8 Dijkstra's algorithm

Dijkstra's algorithm

Relaxing every edge in rounds finds the distances, but it relaxes the same edge many times, and most of those relaxations change nothing. Dijkstra's algorithm relaxes each edge at most once. It deals with the vertices in order of their distance from the source, so that by the time it relaxes the edges leaving a vertex, the distance of that vertex is final. It requires that no weight is negative, which holds for times, lengths and prices, as in this problem:

A network has nn nodes labelled 1 to nn. Each entry times[i] = [u, v, w] is a one-way link: a signal sent from u reaches v after w time units.

A signal leaves node k. Return the time it takes until every node has received it, or -1 if some node never does.

Constraints

  • 1≤k≤n≤1001 \le k \le n \le 100
  • 1≤1 \le times.length ≤6000\le 6000
  • 1≤u,v≤n1 \le u, v \le n and u≠vu \ne v
  • 0≤w≤1000 \le w \le 100
  • No link appears twice

Sample 1 · Input

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

Output

2

Sample 2 · Input

times = [[1,2,1]], n = 2, k = 1

Output

1

Sample 3 · Input

times = [[1,2,1]], n = 2, k = 2

Output

-1

In the first sample the signal starts at node 2. Nodes 1 and 3 receive it after 1 unit of time, and node 3 passes it on to node 4, which receives it at time 1+1=21 + 1 = 2. In the third sample node 2 has no link going out, so node 1 never receives the signal and the answer is −1-1.

The links are the edges of a directed weighted graph, and the signal travels along all of them at once, so a node receives it at a time equal to its distance from node kk. The last node to receive it is the one with the largest distance. The answer is therefore the largest of the distances from kk, or −1-1 if one of them is infinite.

To find the distances, the algorithm marks a vertex as settled once its distance is final. It works as follows:

  1. Set dist to 0 for the source and to ∞\infty for every other vertex. No vertex is settled.
  2. Among the vertices that are not settled, pick the one with the smallest tentative distance.
  3. Mark that vertex as settled, and relax every edge that leaves it.
  4. Repeat steps 2 and 3 until every vertex is settled, or until all the vertices that are left are at ∞\infty.

The vertices that are still at ∞\infty at the end cannot be reached from the source.

The algorithm on the courier map

The samples of the problem are too small to show much, so we run the algorithm on the courier map of the first page, with town 0 as the source:

4121501234

Town 0 is settled first, at distance 0. Its two roads give town 1 the tentative distance 4 and town 2 the tentative distance 1. Of the towns that are not settled, town 2 is now the closest, so it comes next. Its road to town 1 offers 1+2=31 + 2 = 3, which lowers town 1 from 4 to 3, and its road to town 3 gives town 3 the distance 1+5=61 + 5 = 6. Town 1 is next, at 3, and its road lowers town 3 to 3+1=43 + 1 = 4. Town 3 is settled last and has no roads. Town 4 is still at ∞\infty, so the algorithm stops.

The array dist after each step. The highlighted towns are settled.

Each of the five roads was relaxed once, while the rounds of the first page needed 20 relaxations. Town 1 was given the distance 4 at first and was settled later, at 3, when it had become the closest town that was left. A vertex is settled at that moment, and not when it first gets a distance.