Weighted Shortest Paths: Dijkstra, Bellman-Ford and Floyd-Warshall
Editorial
A plain queue or a heap
BFS finds the fewest steps when every step costs the same. Give the steps weights and the fewest steps can be the dearest way. The first fix anyone writes keeps BFS's queue and lets a cell back in whenever a cheaper way to it turns up: right in the end, but in no particular order. Dijkstra's algorithm takes, every time, the cell nearest the start that isn't settled yet, from a heap. Both, on a grid of 300 × 300 cells where every step between two cells weighs from 1 to 100:
import heapq
import time
from collections import deque
N = 300 # a grid of 300 x 300 cells; every step between two has its own weight
x = 7
right, down = [], [] # the weight of the step from a cell to the cell right of it, and below
for _ in range(N * N):
x = x * 48271 % 2147483647
right.append(1 + x % 100)
x = x * 48271 % 2147483647
down.append(1 + x % 100)
def steps(v): # (neighbour, weight) for the four moves
r, c = divmod(v, N)
if r < N - 1:
yield v + N, down[v]
if r > 0:
yield v - N, down[v - N]
if c < N - 1:
yield v + 1, right[v]
if c > 0:
yield v - 1, right[v - 1]
def by_queue(): # BFS with weights: a plain queue, a cell in again whenever it improves
dist = [float("inf")] * (N * N)
dist[0] = 0
queue = deque([0])
taken = 0
while queue:
u = queue.popleft()
taken += 1
for v, w in steps(u):
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
queue.append(v)
return dist[-1], taken
def by_heap(): # Dijkstra: always the nearest cell not settled yet
dist = [float("inf")] * (N * N)
dist[0] = 0
heap = [(0, 0)]
settled = stale = 0
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: # an older, longer entry for a cell settled already
stale += 1
continue
settled += 1
for v, w in steps(u):
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(heap, (dist[v], v))
return dist[-1], settled, stale
print(f"{N} x {N} cells, {2 * N * (N - 1)} steps, each weighing 1 to 100")
start = time.perf_counter()
cost, taken = by_queue()
ms = round((time.perf_counter() - start) * 1000)
print(f"a plain queue: corner to corner costs {cost}, {taken} cells taken off, {ms} ms")
start = time.perf_counter()
cost, settled, stale = by_heap()
ms = round((time.perf_counter() - start) * 1000)
print(f"a heap: corner to corner costs {cost}, {settled} settled, {stale} stale entries skipped, {ms} ms")
# 300 x 300 cells, 179400 steps, each weighing 1 to 100
# a plain queue: corner to corner costs 14340, 1595745 cells taken off, 1416 ms
# a heap: corner to corner costs 14340, 90000 settled, 28518 stale entries skipped, 165 msimport java.util.*;
public class Main {
static final int N = 300; // a grid of 300 x 300 cells; every step has its own weight
static int[] right = new int[N * N], down = new int[N * N]; // the step to the cell right, and the one below
static int[][] steps(int v) { // {neighbour, weight} for the four moves
int r = v / N, c = v % N, k = 0;
int[][] out = new int[4][];
if (r < N - 1) out[k++] = new int[] {v + N, down[v]};
if (r > 0) out[k++] = new int[] {v - N, down[v - N]};
if (c < N - 1) out[k++] = new int[] {v + 1, right[v]};
if (c > 0) out[k++] = new int[] {v - 1, right[v - 1]};
return Arrays.copyOf(out, k);
}
static long[] byQueue() { // BFS with weights: a plain queue, a cell in again when it improves
int[] dist = new int[N * N];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.add(0);
long taken = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
taken++;
for (int[] s : steps(u)) {
if (dist[u] + s[1] < dist[s[0]]) {
dist[s[0]] = dist[u] + s[1];
queue.add(s[0]);
}
}
}
return new long[] {dist[N * N - 1], taken};
}
static long[] byHeap() { // Dijkstra: always the nearest cell not settled yet
int[] dist = new int[N * N];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
: Integer.compare(a[1], b[1]));
heap.add(new int[] {0, 0});
long settled = 0, stale = 0;
while (!heap.isEmpty()) {
int[] top = heap.poll();
int d = top[0], u = top[1];
if (d > dist[u]) { // an older, longer entry for a cell settled already
stale++;
continue;
}
settled++;
for (int[] s : steps(u)) {
if (d + s[1] < dist[s[0]]) {
dist[s[0]] = d + s[1];
heap.add(new int[] {dist[s[0]], s[0]});
}
}
}
return new long[] {dist[N * N - 1], settled, stale};
}
public static void main(String[] args) {
long x = 7;
for (int i = 0; i < N * N; i++) {
x = x * 48271 % 2147483647;
right[i] = (int) (1 + x % 100);
x = x * 48271 % 2147483647;
down[i] = (int) (1 + x % 100);
}
System.out.println(N + " x " + N + " cells, " + 2 * N * (N - 1) + " steps, each weighing 1 to 100");
long start = System.nanoTime();
long[] q = byQueue();
System.out.println("a plain queue: corner to corner costs " + q[0] + ", " + q[1] + " cells taken off, "
+ (System.nanoTime() - start) / 1000000 + " ms");
start = System.nanoTime();
long[] h = byHeap();
System.out.println("a heap: corner to corner costs " + h[0] + ", " + h[1] + " settled, " + h[2]
+ " stale entries skipped, " + (System.nanoTime() - start) / 1000000 + " ms");
}
}
// 300 x 300 cells, 179400 steps, each weighing 1 to 100
// a plain queue: corner to corner costs 14340, 1595745 cells taken off, 218 ms
// a heap: corner to corner costs 14340, 90000 settled, 28518 stale entries skipped, 74 ms#include <bits/stdc++.h>
using namespace std;
const int N = 300; // a grid of 300 x 300 cells; every step has its own weight
vector<int> rightW(N * N), downW(N * N); // the step to the cell right of a cell, and to the one below
vector<pair<int, int>> steps(int v) { // {neighbour, weight} for the four moves
int r = v / N, c = v % N;
vector<pair<int, int>> out;
if (r < N - 1) out.push_back({v + N, downW[v]});
if (r > 0) out.push_back({v - N, downW[v - N]});
if (c < N - 1) out.push_back({v + 1, rightW[v]});
if (c > 0) out.push_back({v - 1, rightW[v - 1]});
return out;
}
pair<int, long long> byQueue() { // BFS with weights: a plain queue, a cell in again when it improves
vector<int> dist(N * N, INT_MAX);
dist[0] = 0;
queue<int> q;
q.push(0);
long long taken = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
taken++;
for (auto [v, w] : steps(u)) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
q.push(v);
}
}
}
return {dist[N * N - 1], taken};
}
tuple<int, long long, long long> byHeap() { // Dijkstra: always the nearest cell not settled yet
vector<int> dist(N * N, INT_MAX);
dist[0] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap;
heap.push({0, 0});
long long settled = 0, stale = 0;
while (!heap.empty()) {
auto [d, u] = heap.top();
heap.pop();
if (d > dist[u]) { // an older, longer entry for a cell settled already
stale++;
continue;
}
settled++;
for (auto [v, w] : steps(u)) {
if (d + w < dist[v]) {
dist[v] = d + w;
heap.push({dist[v], v});
}
}
}
return {dist[N * N - 1], settled, stale};
}
int main() {
long long x = 7;
for (int i = 0; i < N * N; i++) {
x = x * 48271 % 2147483647;
rightW[i] = 1 + x % 100;
x = x * 48271 % 2147483647;
downW[i] = 1 + x % 100;
}
cout << N << " x " << N << " cells, " << 2 * N * (N - 1) << " steps, each weighing 1 to 100\n";
auto start = chrono::steady_clock::now();
auto [cost, taken] = byQueue();
auto ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
cout << "a plain queue: corner to corner costs " << cost << ", " << taken << " cells taken off, " << ms << " ms\n";
start = chrono::steady_clock::now();
auto [cost2, settled, stale] = byHeap();
ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
cout << "a heap: corner to corner costs " << cost2 << ", " << settled << " settled, " << stale
<< " stale entries skipped, " << ms << " ms\n";
}
// 300 x 300 cells, 179400 steps, each weighing 1 to 100
// a plain queue: corner to corner costs 14340, 1595745 cells taken off, 132 ms
// a heap: corner to corner costs 14340, 90000 settled, 28518 stale entries skipped, 19 msclass Heap { // a min-heap of arrays, compared item by item
constructor() { this.a = []; }
get size() { return this.a.length; }
less(i, j) {
const x = this.a[i], y = this.a[j];
for (let k = 0; k < x.length; k++) if (x[k] !== y[k]) return x[k] < y[k];
return false;
}
push(item) {
const a = this.a;
a.push(item);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length) {
a[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(l, m)) m = l;
if (r < a.length && this.less(r, m)) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
const N = 300; // a grid of 300 x 300 cells; every step between two has its own weight
const right = new Array(N * N), down = new Array(N * N); // the step to the cell right of a cell, and to the one below
let x = 7;
for (let i = 0; i < N * N; i++) {
x = x * 48271 % 2147483647;
right[i] = 1 + x % 100;
x = x * 48271 % 2147483647;
down[i] = 1 + x % 100;
}
function steps(v) { // [neighbour, weight] for the four moves
const r = Math.floor(v / N), c = v % N, out = [];
if (r < N - 1) out.push([v + N, down[v]]);
if (r > 0) out.push([v - N, down[v - N]]);
if (c < N - 1) out.push([v + 1, right[v]]);
if (c > 0) out.push([v - 1, right[v - 1]]);
return out;
}
function byQueue() { // BFS with weights: a plain queue, a cell in again whenever it improves
const dist = new Array(N * N).fill(Infinity);
dist[0] = 0;
const queue = [0];
let taken = 0;
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
taken++;
for (const [v, w] of steps(u)) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
queue.push(v);
}
}
}
return [dist[N * N - 1], taken];
}
function byHeap() { // Dijkstra: always the nearest cell not settled yet
const dist = new Array(N * N).fill(Infinity);
dist[0] = 0;
const heap = new Heap();
heap.push([0, 0]);
let settled = 0, stale = 0;
while (heap.size) {
const [d, u] = heap.pop();
if (d > dist[u]) { // an older, longer entry for a cell settled already
stale++;
continue;
}
settled++;
for (const [v, w] of steps(u)) {
if (d + w < dist[v]) {
dist[v] = d + w;
heap.push([dist[v], v]);
}
}
}
return [dist[N * N - 1], settled, stale];
}
console.log(`${N} x ${N} cells, ${2 * N * (N - 1)} steps, each weighing 1 to 100`);
let start = performance.now();
const [cost, taken] = byQueue();
console.log(`a plain queue: corner to corner costs ${cost}, ${taken} cells taken off, ${Math.round(performance.now() - start)} ms`);
start = performance.now();
const [cost2, settled, stale] = byHeap();
console.log(`a heap: corner to corner costs ${cost2}, ${settled} settled, ${stale} stale entries skipped, ${
Math.round(performance.now() - start)} ms`);
// 300 x 300 cells, 179400 steps, each weighing 1 to 100
// a plain queue: corner to corner costs 14340, 1595745 cells taken off, 324 ms
// a heap: corner to corner costs 14340, 90000 settled, 28518 stale entries skipped, 80 msclass Heap { // a min-heap of arrays, compared item by item
private a: number[][] = [];
get size(): number { return this.a.length; }
private less(i: number, j: number): boolean {
const x = this.a[i], y = this.a[j];
for (let k = 0; k < x.length; k++) if (x[k] !== y[k]) return x[k] < y[k];
return false;
}
push(item: number[]): void {
const a = this.a;
a.push(item);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop(): number[] {
const a = this.a, top = a[0], last = a.pop()!;
if (a.length) {
a[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(l, m)) m = l;
if (r < a.length && this.less(r, m)) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
const N = 300; // a grid of 300 x 300 cells; every step between two has its own weight
const right: number[] = new Array(N * N), down: number[] = new Array(N * N); // the step right, and the step down
let x = 7;
for (let i = 0; i < N * N; i++) {
x = x * 48271 % 2147483647;
right[i] = 1 + x % 100;
x = x * 48271 % 2147483647;
down[i] = 1 + x % 100;
}
function steps(v: number): [number, number][] { // [neighbour, weight] for the four moves
const r = Math.floor(v / N), c = v % N, out: [number, number][] = [];
if (r < N - 1) out.push([v + N, down[v]]);
if (r > 0) out.push([v - N, down[v - N]]);
if (c < N - 1) out.push([v + 1, right[v]]);
if (c > 0) out.push([v - 1, right[v - 1]]);
return out;
}
function byQueue(): [number, number] { // BFS with weights: a plain queue, a cell in again whenever it improves
const dist: number[] = new Array(N * N).fill(Infinity);
dist[0] = 0;
const queue = [0];
let taken = 0;
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
taken++;
for (const [v, w] of steps(u)) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
queue.push(v);
}
}
}
return [dist[N * N - 1], taken];
}
function byHeap(): [number, number, number] { // Dijkstra: always the nearest cell not settled yet
const dist: number[] = new Array(N * N).fill(Infinity);
dist[0] = 0;
const heap = new Heap();
heap.push([0, 0]);
let settled = 0, stale = 0;
while (heap.size) {
const [d, u] = heap.pop();
if (d > dist[u]) { // an older, longer entry for a cell settled already
stale++;
continue;
}
settled++;
for (const [v, w] of steps(u)) {
if (d + w < dist[v]) {
dist[v] = d + w;
heap.push([dist[v], v]);
}
}
}
return [dist[N * N - 1], settled, stale];
}
console.log(`${N} x ${N} cells, ${2 * N * (N - 1)} steps, each weighing 1 to 100`);
let start = performance.now();
const [cost, taken] = byQueue();
console.log(`a plain queue: corner to corner costs ${cost}, ${taken} cells taken off, ${Math.round(performance.now() - start)} ms`);
start = performance.now();
const [cost2, settled, stale] = byHeap();
console.log(`a heap: corner to corner costs ${cost2}, ${settled} settled, ${stale} stale entries skipped, ${
Math.round(performance.now() - start)} ms`);
// 300 x 300 cells, 179400 steps, each weighing 1 to 100
// a plain queue: corner to corner costs 14340, 1595745 cells taken off, 316 ms
// a heap: corner to corner costs 14340, 90000 settled, 28518 stale entries skipped, 82 msusing System;
using System.Collections.Generic;
using System.Diagnostics;
class Program {
const int N = 300; // a grid of 300 x 300 cells; every step has its own weight
static int[] right = new int[N * N], down = new int[N * N]; // the step to the cell right, and the one below
static List<(int v, int w)> Steps(int v) { // (neighbour, weight) for the four moves
int r = v / N, c = v % N;
var output = new List<(int, int)>(4);
if (r < N - 1) output.Add((v + N, down[v]));
if (r > 0) output.Add((v - N, down[v - N]));
if (c < N - 1) output.Add((v + 1, right[v]));
if (c > 0) output.Add((v - 1, right[v - 1]));
return output;
}
static (int, long) ByQueue() { // BFS with weights: a plain queue, a cell in again when it improves
var dist = new int[N * N];
Array.Fill(dist, int.MaxValue);
dist[0] = 0;
var queue = new Queue<int>();
queue.Enqueue(0);
long taken = 0;
while (queue.Count > 0) {
int u = queue.Dequeue();
taken++;
foreach (var (v, w) in Steps(u)) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
queue.Enqueue(v);
}
}
}
return (dist[N * N - 1], taken);
}
static (int, long, long) ByHeap() { // Dijkstra: always the nearest cell not settled yet
var dist = new int[N * N];
Array.Fill(dist, int.MaxValue);
dist[0] = 0;
var heap = new PriorityQueue<int, (int, int)>(); // ordered by (distance, cell)
heap.Enqueue(0, (0, 0));
long settled = 0, stale = 0;
while (heap.TryDequeue(out int u, out var key)) {
int d = key.Item1;
if (d > dist[u]) { // an older, longer entry for a cell settled already
stale++;
continue;
}
settled++;
foreach (var (v, w) in Steps(u)) {
if (d + w < dist[v]) {
dist[v] = d + w;
heap.Enqueue(v, (dist[v], v));
}
}
}
return (dist[N * N - 1], settled, stale);
}
static void Main() {
long x = 7;
for (int i = 0; i < N * N; i++) {
x = x * 48271 % 2147483647;
right[i] = (int) (1 + x % 100);
x = x * 48271 % 2147483647;
down[i] = (int) (1 + x % 100);
}
Console.WriteLine($"{N} x {N} cells, {2 * N * (N - 1)} steps, each weighing 1 to 100");
var watch = Stopwatch.StartNew();
var (cost, taken) = ByQueue();
Console.WriteLine($"a plain queue: corner to corner costs {cost}, {taken} cells taken off, {watch.ElapsedMilliseconds} ms");
watch.Restart();
var (cost2, settled, stale) = ByHeap();
Console.WriteLine($"a heap: corner to corner costs {cost2}, {settled} settled, {stale} stale entries skipped, {watch.ElapsedMilliseconds} ms");
}
}
// 300 x 300 cells, 179400 steps, each weighing 1 to 100
// a plain queue: corner to corner costs 14340, 1595745 cells taken off, 105 ms
// a heap: corner to corner costs 14340, 90000 settled, 28518 stale entries skipped, 32 mspackage main
import (
"container/heap"
"fmt"
"math"
"time"
)
type item struct{ d, v int }
type minHeap []item // the smallest distance on top, the smaller vertex first on a tie
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].d < h[j].d || (h[i].d == h[j].d && h[i].v < h[j].v) }
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
const N = 300 // a grid of 300 x 300 cells; every step between two has its own weight
var right, down [N * N]int // the weight of the step to the cell right of a cell, and to the one below
func steps(v int) [][2]int { // {neighbour, weight} for the four moves
r, c := v/N, v%N
out := make([][2]int, 0, 4)
if r < N-1 {
out = append(out, [2]int{v + N, down[v]})
}
if r > 0 {
out = append(out, [2]int{v - N, down[v-N]})
}
if c < N-1 {
out = append(out, [2]int{v + 1, right[v]})
}
if c > 0 {
out = append(out, [2]int{v - 1, right[v-1]})
}
return out
}
func byQueue() (int, int) { // BFS with weights: a plain queue, a cell in again whenever it improves
dist := make([]int, N*N)
for i := range dist {
dist[i] = math.MaxInt64
}
dist[0] = 0
queue := []int{0}
taken := 0
for head := 0; head < len(queue); head++ {
u := queue[head]
taken++
for _, s := range steps(u) {
if dist[u]+s[1] < dist[s[0]] {
dist[s[0]] = dist[u] + s[1]
queue = append(queue, s[0])
}
}
}
return dist[N*N-1], taken
}
func byHeap() (int, int, int) { // Dijkstra: always the nearest cell not settled yet
dist := make([]int, N*N)
for i := range dist {
dist[i] = math.MaxInt64
}
dist[0] = 0
h := &minHeap{{0, 0}}
settled, stale := 0, 0
for h.Len() > 0 {
top := heap.Pop(h).(item)
if top.d > dist[top.v] { // an older, longer entry for a cell settled already
stale++
continue
}
settled++
for _, s := range steps(top.v) {
if top.d+s[1] < dist[s[0]] {
dist[s[0]] = top.d + s[1]
heap.Push(h, item{dist[s[0]], s[0]})
}
}
}
return dist[N*N-1], settled, stale
}
func main() {
x := 7
for i := 0; i < N*N; i++ {
x = x * 48271 % 2147483647
right[i] = 1 + x%100
x = x * 48271 % 2147483647
down[i] = 1 + x%100
}
fmt.Printf("%d x %d cells, %d steps, each weighing 1 to 100\n", N, N, 2*N*(N-1))
start := time.Now()
cost, taken := byQueue()
fmt.Printf("a plain queue: corner to corner costs %d, %d cells taken off, %d ms\n", cost, taken, time.Since(start).Milliseconds())
start = time.Now()
cost, settled, stale := byHeap()
fmt.Printf("a heap: corner to corner costs %d, %d settled, %d stale entries skipped, %d ms\n", cost, settled, stale,
time.Since(start).Milliseconds())
}
// 300 x 300 cells, 179400 steps, each weighing 1 to 100
// a plain queue: corner to corner costs 14340, 1595745 cells taken off, 211 ms
// a heap: corner to corner costs 14340, 90000 settled, 28518 stale entries skipped, 36 msBoth reach the far corner for 14,340, in every language. The plain queue took cells off 1,595,745 times, about 18 times each: a cell reached early by a dear way had to be taken again for every cheaper way that turned up later, and everything after it with it. The heap settled each of the 90,000 cells once and skipped 28,518 entries left over from ways that were beaten later. In Python that was 1,416 ms against 165 ms, and the heap was faster in every language.
Dijkstra: settle the nearest
Why taking the nearest works: every other vertex waiting is at least as far, and no weight is negative, so no way through them can come back cheaper. The nearest is settled, final. Then relax its edges: for each neighbour, if going through it is cheaper, lower the neighbour's distance and push it on the heap again. The old entry stays in the heap; when it comes off later, longer than the distance now known, skip it. Network Delay Time asks when the last node hears a signal sent from k: the largest of these distances.
import heapq
def network_delay(times, n, k): # Network Delay Time: times[i] = [from, to, minutes], nodes 1 to n
adj = [[] for _ in range(n + 1)]
for u, v, w in times:
adj[u].append((v, w))
dist, parent = [float("inf")] * (n + 1), [0] * (n + 1)
dist[k] = 0
heap, settled, stale = [(0, k)], [], 0
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: # a longer entry left behind when u improved: skip it
stale += 1
continue
settled.append(u) # the nearest not settled yet: nothing found later can beat d
for v, w in adj[u]:
if d + w < dist[v]:
dist[v], parent[v] = d + w, u
heapq.heappush(heap, (dist[v], v))
return dist, parent, settled, stale
times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1], [3, 4, 5], [4, 5, 3], [5, 6, 1], [3, 6, 9]]
dist, parent, settled, stale = network_delay(times, 6, 1)
print("times from 1:", " ".join(map(str, dist[1:])))
print("settled:", " ".join(map(str, settled)) + f", with {stale} stale entries skipped")
last = max(range(1, 7), key=lambda v: dist[v])
route = [last]
while route[-1] != 1: # read the route back from the last node to hear
route.append(parent[route[-1]])
print(f"all 6 have it after {dist[last]}; the last, {last}, by", " -> ".join(map(str, route[::-1])))
# times from 1: 0 3 1 4 7 8
# settled: 1 3 2 4 5 6, with 3 stale entries skipped
# all 6 have it after 8; the last, 6, by 1 -> 3 -> 2 -> 4 -> 5 -> 6import java.util.*;
public class Main {
public static void main(String[] args) {
int[][] times = {{1, 2, 4}, {1, 3, 1}, {3, 2, 2}, {2, 4, 1}, {3, 4, 5}, {4, 5, 3}, {5, 6, 1}, {3, 6, 9}};
int n = 6, k = 1; // Network Delay Time: {from, to, minutes}, nodes 1 to n
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int[] t : times) adj.get(t[0]).add(new int[] {t[1], t[2]});
int[] dist = new int[n + 1], parent = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[k] = 0;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
: Integer.compare(a[1], b[1]));
heap.add(new int[] {0, k});
List<Integer> settled = new ArrayList<>();
int stale = 0;
while (!heap.isEmpty()) {
int[] top = heap.poll();
int d = top[0], u = top[1];
if (d > dist[u]) { // a longer entry left behind when u improved: skip it
stale++;
continue;
}
settled.add(u); // the nearest not settled yet: nothing found later can beat d
for (int[] e : adj.get(u)) {
if (d + e[1] < dist[e[0]]) {
dist[e[0]] = d + e[1];
parent[e[0]] = u;
heap.add(new int[] {dist[e[0]], e[0]});
}
}
}
StringJoiner ds = new StringJoiner(" "), ss = new StringJoiner(" ");
for (int v = 1; v <= n; v++) ds.add(String.valueOf(dist[v]));
for (int v : settled) ss.add(String.valueOf(v));
System.out.println("times from 1: " + ds);
System.out.println("settled: " + ss + ", with " + stale + " stale entries skipped");
int last = 1;
for (int v = 1; v <= n; v++) if (dist[v] > dist[last]) last = v;
LinkedList<Integer> route = new LinkedList<>();
for (int v = last; v != k; v = parent[v]) route.addFirst(v); // read the route back from the last to hear
route.addFirst(k);
StringJoiner rs = new StringJoiner(" -> ");
for (int v : route) rs.add(String.valueOf(v));
System.out.println("all 6 have it after " + dist[last] + "; the last, " + last + ", by " + rs);
}
}
// times from 1: 0 3 1 4 7 8
// settled: 1 3 2 4 5 6, with 3 stale entries skipped
// all 6 have it after 8; the last, 6, by 1 -> 3 -> 2 -> 4 -> 5 -> 6#include <bits/stdc++.h>
using namespace std;
int main() {
vector<array<int, 3>> times = {{1, 2, 4}, {1, 3, 1}, {3, 2, 2}, {2, 4, 1}, {3, 4, 5}, {4, 5, 3}, {5, 6, 1}, {3, 6, 9}};
int n = 6, k = 1; // Network Delay Time: {from, to, minutes}, nodes 1 to n
vector<vector<pair<int, int>>> adj(n + 1);
for (auto& t : times) adj[t[0]].push_back({t[1], t[2]});
vector<int> dist(n + 1, INT_MAX), parent(n + 1, 0), settled;
dist[k] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap;
heap.push({0, k});
int stale = 0;
while (!heap.empty()) {
auto [d, u] = heap.top();
heap.pop();
if (d > dist[u]) { // a longer entry left behind when u improved: skip it
stale++;
continue;
}
settled.push_back(u); // the nearest not settled yet: nothing found later can beat d
for (auto [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
parent[v] = u;
heap.push({dist[v], v});
}
}
}
cout << "times from 1:";
for (int v = 1; v <= n; v++) cout << " " << dist[v];
cout << "\nsettled:";
for (size_t i = 0; i < settled.size(); i++) cout << (i ? " " : " ") << settled[i];
cout << ", with " << stale << " stale entries skipped\n";
int last = 1;
for (int v = 1; v <= n; v++) if (dist[v] > dist[last]) last = v;
vector<int> route;
for (int v = last; v != k; v = parent[v]) route.push_back(v); // read the route back from the last to hear
route.push_back(k);
reverse(route.begin(), route.end());
cout << "all 6 have it after " << dist[last] << "; the last, " << last << ", by";
for (size_t i = 0; i < route.size(); i++) cout << (i ? " -> " : " ") << route[i];
cout << "\n";
}
// times from 1: 0 3 1 4 7 8
// settled: 1 3 2 4 5 6, with 3 stale entries skipped
// all 6 have it after 8; the last, 6, by 1 -> 3 -> 2 -> 4 -> 5 -> 6class Heap { // a min-heap of arrays, compared item by item
constructor() { this.a = []; }
get size() { return this.a.length; }
less(i, j) {
const x = this.a[i], y = this.a[j];
for (let k = 0; k < x.length; k++) if (x[k] !== y[k]) return x[k] < y[k];
return false;
}
push(item) {
const a = this.a;
a.push(item);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length) {
a[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(l, m)) m = l;
if (r < a.length && this.less(r, m)) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
const times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1], [3, 4, 5], [4, 5, 3], [5, 6, 1], [3, 6, 9]];
const n = 6, k = 1; // Network Delay Time: [from, to, minutes], nodes 1 to n
const adj = Array.from({ length: n + 1 }, () => []);
for (const [u, v, w] of times) adj[u].push([v, w]);
const dist = new Array(n + 1).fill(Infinity), parent = new Array(n + 1).fill(0);
dist[k] = 0;
const heap = new Heap();
heap.push([0, k]);
const settled = [];
let stale = 0;
while (heap.size) {
const [d, u] = heap.pop();
if (d > dist[u]) { // a longer entry left behind when u improved: skip it
stale++;
continue;
}
settled.push(u); // the nearest not settled yet: nothing found later can beat d
for (const [v, w] of adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
parent[v] = u;
heap.push([dist[v], v]);
}
}
}
console.log(`times from 1: ${dist.slice(1).join(" ")}`);
console.log(`settled: ${settled.join(" ")}, with ${stale} stale entries skipped`);
let last = 1;
for (let v = 1; v <= n; v++) if (dist[v] > dist[last]) last = v;
const route = [last];
while (route[route.length - 1] !== k) route.push(parent[route[route.length - 1]]); // read the route back
console.log(`all 6 have it after ${dist[last]}; the last, ${last}, by ${route.reverse().join(" -> ")}`);
// times from 1: 0 3 1 4 7 8
// settled: 1 3 2 4 5 6, with 3 stale entries skipped
// all 6 have it after 8; the last, 6, by 1 -> 3 -> 2 -> 4 -> 5 -> 6class Heap { // a min-heap of arrays, compared item by item
private a: number[][] = [];
get size(): number { return this.a.length; }
private less(i: number, j: number): boolean {
const x = this.a[i], y = this.a[j];
for (let k = 0; k < x.length; k++) if (x[k] !== y[k]) return x[k] < y[k];
return false;
}
push(item: number[]): void {
const a = this.a;
a.push(item);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop(): number[] {
const a = this.a, top = a[0], last = a.pop()!;
if (a.length) {
a[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(l, m)) m = l;
if (r < a.length && this.less(r, m)) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
const times: [number, number, number][] = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1], [3, 4, 5], [4, 5, 3], [5, 6, 1],
[3, 6, 9]];
const n = 6, k = 1; // Network Delay Time: [from, to, minutes], nodes 1 to n
const adj: [number, number][][] = Array.from({ length: n + 1 }, () => []);
for (const [u, v, w] of times) adj[u].push([v, w]);
const dist: number[] = new Array(n + 1).fill(Infinity), parent: number[] = new Array(n + 1).fill(0);
dist[k] = 0;
const heap = new Heap();
heap.push([0, k]);
const settled: number[] = [];
let stale = 0;
while (heap.size) {
const [d, u] = heap.pop();
if (d > dist[u]) { // a longer entry left behind when u improved: skip it
stale++;
continue;
}
settled.push(u); // the nearest not settled yet: nothing found later can beat d
for (const [v, w] of adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
parent[v] = u;
heap.push([dist[v], v]);
}
}
}
console.log(`times from 1: ${dist.slice(1).join(" ")}`);
console.log(`settled: ${settled.join(" ")}, with ${stale} stale entries skipped`);
let last = 1;
for (let v = 1; v <= n; v++) if (dist[v] > dist[last]) last = v;
const route = [last];
while (route[route.length - 1] !== k) route.push(parent[route[route.length - 1]]); // read the route back
console.log(`all 6 have it after ${dist[last]}; the last, ${last}, by ${route.reverse().join(" -> ")}`);
// times from 1: 0 3 1 4 7 8
// settled: 1 3 2 4 5 6, with 3 stale entries skipped
// all 6 have it after 8; the last, 6, by 1 -> 3 -> 2 -> 4 -> 5 -> 6using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static void Main() {
int[][] times = { new[] {1, 2, 4}, new[] {1, 3, 1}, new[] {3, 2, 2}, new[] {2, 4, 1}, new[] {3, 4, 5},
new[] {4, 5, 3}, new[] {5, 6, 1}, new[] {3, 6, 9} };
int n = 6, k = 1; // Network Delay Time: {from, to, minutes}, nodes 1 to n
var adj = new List<(int v, int w)>[n + 1];
for (int i = 0; i <= n; i++) adj[i] = new List<(int, int)>();
foreach (var t in times) adj[t[0]].Add((t[1], t[2]));
var dist = new int[n + 1];
var parent = new int[n + 1];
Array.Fill(dist, int.MaxValue);
dist[k] = 0;
var heap = new PriorityQueue<int, (int, int)>(); // ordered by (distance, node)
heap.Enqueue(k, (0, k));
var settled = new List<int>();
int stale = 0;
while (heap.TryDequeue(out int u, out var key)) {
int d = key.Item1;
if (d > dist[u]) { // a longer entry left behind when u improved: skip it
stale++;
continue;
}
settled.Add(u); // the nearest not settled yet: nothing found later can beat d
foreach (var (v, w) in adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
parent[v] = u;
heap.Enqueue(v, (dist[v], v));
}
}
}
Console.WriteLine($"times from 1: {string.Join(" ", dist.Skip(1))}");
Console.WriteLine($"settled: {string.Join(" ", settled)}, with {stale} stale entries skipped");
int last = 1;
for (int v = 1; v <= n; v++) if (dist[v] > dist[last]) last = v;
var route = new List<int>();
for (int v = last; v != k; v = parent[v]) route.Insert(0, v); // read the route back from the last to hear
route.Insert(0, k);
Console.WriteLine($"all 6 have it after {dist[last]}; the last, {last}, by {string.Join(" -> ", route)}");
}
}
// times from 1: 0 3 1 4 7 8
// settled: 1 3 2 4 5 6, with 3 stale entries skipped
// all 6 have it after 8; the last, 6, by 1 -> 3 -> 2 -> 4 -> 5 -> 6package main
import (
"container/heap"
"fmt"
"math"
"strconv"
"strings"
)
type item struct{ d, v int }
type minHeap []item // the smallest distance on top, the smaller vertex first on a tie
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].d < h[j].d || (h[i].d == h[j].d && h[i].v < h[j].v) }
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func joined(xs []int, sep string) string {
parts := make([]string, len(xs))
for i, x := range xs {
parts[i] = strconv.Itoa(x)
}
return strings.Join(parts, sep)
}
func main() {
times := [][3]int{{1, 2, 4}, {1, 3, 1}, {3, 2, 2}, {2, 4, 1}, {3, 4, 5}, {4, 5, 3}, {5, 6, 1}, {3, 6, 9}}
n, k := 6, 1 // Network Delay Time: {from, to, minutes}, nodes 1 to n
adj := make([][][2]int, n+1)
for _, t := range times {
adj[t[0]] = append(adj[t[0]], [2]int{t[1], t[2]})
}
dist, parent := make([]int, n+1), make([]int, n+1)
for i := range dist {
dist[i] = math.MaxInt64
}
dist[k] = 0
h := &minHeap{{0, k}}
settled, stale := []int{}, 0
for h.Len() > 0 {
top := heap.Pop(h).(item)
if top.d > dist[top.v] { // a longer entry left behind when v improved: skip it
stale++
continue
}
settled = append(settled, top.v) // the nearest not settled yet: nothing found later can beat d
for _, e := range adj[top.v] {
if top.d+e[1] < dist[e[0]] {
dist[e[0]], parent[e[0]] = top.d+e[1], top.v
heap.Push(h, item{dist[e[0]], e[0]})
}
}
}
fmt.Println("times from 1:", joined(dist[1:], " "))
fmt.Printf("settled: %s, with %d stale entries skipped\n", joined(settled, " "), stale)
last := 1
for v := 1; v <= n; v++ {
if dist[v] > dist[last] {
last = v
}
}
route := []int{}
for v := last; v != k; v = parent[v] { // read the route back from the last to hear
route = append([]int{v}, route...)
}
route = append([]int{k}, route...)
fmt.Printf("all 6 have it after %d; the last, %d, by %s\n", dist[last], last, joined(route, " -> "))
}
// times from 1: 0 3 1 4 7 8
// settled: 1 3 2 4 5 6, with 3 stale entries skipped
// all 6 have it after 8; the last, 6, by 1 -> 3 -> 2 -> 4 -> 5 -> 6After 1 itself, node 3 comes off at 1 and lowers 2 from 4 to 3, leaving 2's old 4 in the heap. 4's first entry, 6 through 3, is beaten by 4 through 2, and 6's 10 by 8 through 5: with 2's old 4, those are the 3 stale entries. The last to hear is 6, after 8, along 1 → 3 → 2 → 4 → 5 → 6, read back from the parents. With a binary heap that's O((V + E) log V). Dijkstra's Algorithm asks for exactly these distances, and Dijkstra: Queue vs Priority Queue for the difference the grid above showed.
Settle the Nearest. Run it yourself: settle the nearest node each time and watch its edges relax; then take the heap's entries off one by one, settling each or skipping it as stale; then read 6's route back to 1 from the parents.
A negative edge
The proof leaned on one fact: no weight is negative. Break it, and a vertex settled early can be undercut later, through a vertex that was still waiting:
import heapq
edges = [(0, 1, 2), (0, 2, 5), (2, 1, -4), (1, 3, 1)] # the edge 2 -> 1 weighs -4
n = 4
adj = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append((v, w))
dist, done = [float("inf")] * n, [False] * n # Dijkstra: a vertex is final once it comes off the heap
dist[0] = 0
heap = [(0, 0)]
while heap:
d, u = heapq.heappop(heap)
if done[u]:
continue
done[u] = True
for v, w in adj[u]:
if not done[v] and d + w < dist[v]:
dist[v] = d + w
heapq.heappush(heap, (dist[v], v))
print("Dijkstra:", " ".join(map(str, dist)))
best = [float("inf")] * n # Bellman-Ford: every edge, n - 1 times over
best[0] = 0
for _ in range(n - 1):
for u, v, w in edges:
if best[u] + w < best[v]:
best[v] = best[u] + w
print("Bellman-Ford:", " ".join(map(str, best)))
# Dijkstra: 0 2 5 3
# Bellman-Ford: 0 1 5 2import java.util.*;
public class Main {
public static void main(String[] args) {
int[][] edges = {{0, 1, 2}, {0, 2, 5}, {2, 1, -4}, {1, 3, 1}}; // the edge 2 -> 1 weighs -4
int n = 4;
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) adj.get(e[0]).add(new int[] {e[1], e[2]});
int[] dist = new int[n]; // Dijkstra: a vertex is final once it comes off the heap
boolean[] done = new boolean[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
: Integer.compare(a[1], b[1]));
heap.add(new int[] {0, 0});
while (!heap.isEmpty()) {
int[] top = heap.poll();
int d = top[0], u = top[1];
if (done[u]) continue;
done[u] = true;
for (int[] e : adj.get(u)) {
if (!done[e[0]] && d + e[1] < dist[e[0]]) {
dist[e[0]] = d + e[1];
heap.add(new int[] {dist[e[0]], e[0]});
}
}
}
StringJoiner a = new StringJoiner(" ");
for (int d : dist) a.add(String.valueOf(d));
System.out.println("Dijkstra: " + a);
int[] best = new int[n]; // Bellman-Ford: every edge, n - 1 times over
Arrays.fill(best, Integer.MAX_VALUE);
best[0] = 0;
for (int round = 0; round < n - 1; round++) {
for (int[] e : edges) {
if (best[e[0]] != Integer.MAX_VALUE && best[e[0]] + e[2] < best[e[1]]) best[e[1]] = best[e[0]] + e[2];
}
}
StringJoiner b = new StringJoiner(" ");
for (int d : best) b.add(String.valueOf(d));
System.out.println("Bellman-Ford: " + b);
}
}
// Dijkstra: 0 2 5 3
// Bellman-Ford: 0 1 5 2#include <bits/stdc++.h>
using namespace std;
int main() {
vector<array<int, 3>> edges = {{0, 1, 2}, {0, 2, 5}, {2, 1, -4}, {1, 3, 1}}; // the edge 2 -> 1 weighs -4
int n = 4;
vector<vector<pair<int, int>>> adj(n);
for (auto& e : edges) adj[e[0]].push_back({e[1], e[2]});
vector<int> dist(n, INT_MAX); // Dijkstra: a vertex is final once it comes off the heap
vector<char> done(n, 0);
dist[0] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap;
heap.push({0, 0});
while (!heap.empty()) {
auto [d, u] = heap.top();
heap.pop();
if (done[u]) continue;
done[u] = 1;
for (auto [v, w] : adj[u]) {
if (!done[v] && d + w < dist[v]) {
dist[v] = d + w;
heap.push({dist[v], v});
}
}
}
cout << "Dijkstra:";
for (int d : dist) cout << " " << d;
cout << "\n";
vector<int> best(n, INT_MAX); // Bellman-Ford: every edge, n - 1 times over
best[0] = 0;
for (int round = 0; round < n - 1; round++)
for (auto& e : edges)
if (best[e[0]] != INT_MAX && best[e[0]] + e[2] < best[e[1]]) best[e[1]] = best[e[0]] + e[2];
cout << "Bellman-Ford:";
for (int d : best) cout << " " << d;
cout << "\n";
}
// Dijkstra: 0 2 5 3
// Bellman-Ford: 0 1 5 2class Heap { // a min-heap of arrays, compared item by item
constructor() { this.a = []; }
get size() { return this.a.length; }
less(i, j) {
const x = this.a[i], y = this.a[j];
for (let k = 0; k < x.length; k++) if (x[k] !== y[k]) return x[k] < y[k];
return false;
}
push(item) {
const a = this.a;
a.push(item);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length) {
a[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(l, m)) m = l;
if (r < a.length && this.less(r, m)) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
const edges = [[0, 1, 2], [0, 2, 5], [2, 1, -4], [1, 3, 1]]; // the edge 2 -> 1 weighs -4
const n = 4;
const adj = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) adj[u].push([v, w]);
const dist = new Array(n).fill(Infinity), done = new Array(n).fill(false); // Dijkstra: final once off the heap
dist[0] = 0;
const heap = new Heap();
heap.push([0, 0]);
while (heap.size) {
const [d, u] = heap.pop();
if (done[u]) continue;
done[u] = true;
for (const [v, w] of adj[u]) {
if (!done[v] && d + w < dist[v]) {
dist[v] = d + w;
heap.push([dist[v], v]);
}
}
}
console.log(`Dijkstra: ${dist.join(" ")}`);
const best = new Array(n).fill(Infinity); // Bellman-Ford: every edge, n - 1 times over
best[0] = 0;
for (let round = 0; round < n - 1; round++)
for (const [u, v, w] of edges) if (best[u] + w < best[v]) best[v] = best[u] + w;
console.log(`Bellman-Ford: ${best.join(" ")}`);
// Dijkstra: 0 2 5 3
// Bellman-Ford: 0 1 5 2class Heap { // a min-heap of arrays, compared item by item
private a: number[][] = [];
get size(): number { return this.a.length; }
private less(i: number, j: number): boolean {
const x = this.a[i], y = this.a[j];
for (let k = 0; k < x.length; k++) if (x[k] !== y[k]) return x[k] < y[k];
return false;
}
push(item: number[]): void {
const a = this.a;
a.push(item);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop(): number[] {
const a = this.a, top = a[0], last = a.pop()!;
if (a.length) {
a[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(l, m)) m = l;
if (r < a.length && this.less(r, m)) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
const edges: [number, number, number][] = [[0, 1, 2], [0, 2, 5], [2, 1, -4], [1, 3, 1]]; // 2 -> 1 weighs -4
const n = 4;
const adj: [number, number][][] = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) adj[u].push([v, w]);
const dist: number[] = new Array(n).fill(Infinity); // Dijkstra: a vertex is final once it comes off the heap
const done: boolean[] = new Array(n).fill(false);
dist[0] = 0;
const heap = new Heap();
heap.push([0, 0]);
while (heap.size) {
const [d, u] = heap.pop();
if (done[u]) continue;
done[u] = true;
for (const [v, w] of adj[u]) {
if (!done[v] && d + w < dist[v]) {
dist[v] = d + w;
heap.push([dist[v], v]);
}
}
}
console.log(`Dijkstra: ${dist.join(" ")}`);
const best: number[] = new Array(n).fill(Infinity); // Bellman-Ford: every edge, n - 1 times over
best[0] = 0;
for (let round = 0; round < n - 1; round++)
for (const [u, v, w] of edges) if (best[u] + w < best[v]) best[v] = best[u] + w;
console.log(`Bellman-Ford: ${best.join(" ")}`);
// Dijkstra: 0 2 5 3
// Bellman-Ford: 0 1 5 2using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[][] edges = { new[] {0, 1, 2}, new[] {0, 2, 5}, new[] {2, 1, -4}, new[] {1, 3, 1} }; // 2 -> 1 weighs -4
int n = 4;
var adj = new List<(int v, int w)>[n];
for (int i = 0; i < n; i++) adj[i] = new List<(int, int)>();
foreach (var e in edges) adj[e[0]].Add((e[1], e[2]));
var dist = new int[n]; // Dijkstra: a vertex is final once it comes off the heap
var done = new bool[n];
Array.Fill(dist, int.MaxValue);
dist[0] = 0;
var heap = new PriorityQueue<int, (int, int)>();
heap.Enqueue(0, (0, 0));
while (heap.TryDequeue(out int u, out var key)) {
int d = key.Item1;
if (done[u]) continue;
done[u] = true;
foreach (var (v, w) in adj[u]) {
if (!done[v] && d + w < dist[v]) {
dist[v] = d + w;
heap.Enqueue(v, (dist[v], v));
}
}
}
Console.WriteLine($"Dijkstra: {string.Join(" ", dist)}");
var best = new int[n]; // Bellman-Ford: every edge, n - 1 times over
Array.Fill(best, int.MaxValue);
best[0] = 0;
for (int round = 0; round < n - 1; round++)
foreach (var e in edges)
if (best[e[0]] != int.MaxValue && best[e[0]] + e[2] < best[e[1]]) best[e[1]] = best[e[0]] + e[2];
Console.WriteLine($"Bellman-Ford: {string.Join(" ", best)}");
}
}
// Dijkstra: 0 2 5 3
// Bellman-Ford: 0 1 5 2package main
import (
"container/heap"
"fmt"
"math"
"strconv"
"strings"
)
type item struct{ d, v int }
type minHeap []item // the smallest distance on top, the smaller vertex first on a tie
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].d < h[j].d || (h[i].d == h[j].d && h[i].v < h[j].v) }
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func joined(xs []int) string {
parts := make([]string, len(xs))
for i, x := range xs {
parts[i] = strconv.Itoa(x)
}
return strings.Join(parts, " ")
}
func main() {
edges := [][3]int{{0, 1, 2}, {0, 2, 5}, {2, 1, -4}, {1, 3, 1}} // the edge 2 -> 1 weighs -4
n := 4
adj := make([][][2]int, n)
for _, e := range edges {
adj[e[0]] = append(adj[e[0]], [2]int{e[1], e[2]})
}
dist, done := make([]int, n), make([]bool, n) // Dijkstra: a vertex is final once it comes off the heap
for i := range dist {
dist[i] = math.MaxInt64
}
dist[0] = 0
h := &minHeap{{0, 0}}
for h.Len() > 0 {
top := heap.Pop(h).(item)
if done[top.v] {
continue
}
done[top.v] = true
for _, e := range adj[top.v] {
if !done[e[0]] && top.d+e[1] < dist[e[0]] {
dist[e[0]] = top.d + e[1]
heap.Push(h, item{dist[e[0]], e[0]})
}
}
}
fmt.Println("Dijkstra:", joined(dist))
best := make([]int, n) // Bellman-Ford: every edge, n - 1 times over
for i := range best {
best[i] = math.MaxInt64
}
best[0] = 0
for round := 0; round < n-1; round++ {
for _, e := range edges {
if best[e[0]] != math.MaxInt64 && best[e[0]]+e[2] < best[e[1]] {
best[e[1]] = best[e[0]] + e[2]
}
}
}
fmt.Println("Bellman-Ford:", joined(best))
}
// Dijkstra: 0 2 5 3
// Bellman-Ford: 0 1 5 2Dijkstra settled 1 at 2, straight from 0, and then 3 at 3 through it. Only after that did 2 come off, at 5, with its edge of −4 back to 1. 1 was final already, so the cheaper way, 5 − 4 = 1, was never used, and neither was the 2 it would have given 3. Bellman-Ford trusts no order: it relaxes every edge, round after round, and gets 0 1 5 2. When weights can be negative it's the one to reach for, at a price.
The largest step, not the sum
Path With Minimum Effort measures a route by its largest climb or drop between neighbouring cells, not by their sum. Dijkstra still works with max where the sum was: extending a route never makes its largest step smaller, so the nearest-first promise still holds:
import heapq
def least_effort(heights): # Path With Minimum Effort: a route costs its largest climb or drop
R, C = len(heights), len(heights[0])
best = [[float("inf")] * C for _ in range(R)]
parent = [[None] * C for _ in range(R)]
best[0][0] = 0
heap = [(0, 0, 0)]
while heap:
e, r, c = heapq.heappop(heap)
if e > best[r][c]:
continue
if (r, c) == (R - 1, C - 1):
break
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C:
ne = max(e, abs(heights[nr][nc] - heights[r][c])) # max in place of +: never smaller than e
if ne < best[nr][nc]:
best[nr][nc], parent[nr][nc] = ne, (r, c)
heapq.heappush(heap, (ne, nr, nc))
route, cell = [], (R - 1, C - 1)
while cell:
route.append(heights[cell[0]][cell[1]])
cell = parent[cell[0]][cell[1]]
return best[R - 1][C - 1], route[::-1]
effort, route = least_effort([[4, 8, 6], [7, 1, 9], [5, 3, 2]])
print("the least effort, corner to corner:", effort, "| by the heights", " ".join(map(str, route)))
# the least effort, corner to corner: 3 | by the heights 4 7 5 3 2import java.util.*;
public class Main {
public static void main(String[] args) {
int[][] heights = {{4, 8, 6}, {7, 1, 9}, {5, 3, 2}}; // Path With Minimum Effort: a route costs its largest step
int R = heights.length, C = heights[0].length;
int[][] best = new int[R][C], parent = new int[R][C];
for (int[] row : best) Arrays.fill(row, Integer.MAX_VALUE);
best[0][0] = 0;
parent[0][0] = -1;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
: Integer.compare(a[1], b[1]));
heap.add(new int[] {0, 0}); // {effort, cell r * C + c}
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!heap.isEmpty()) {
int[] top = heap.poll();
int e = top[0], r = top[1] / C, c = top[1] % C;
if (e > best[r][c]) continue;
if (r == R - 1 && c == C - 1) break;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
int ne = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c])); // max in place of +
if (ne < best[nr][nc]) {
best[nr][nc] = ne;
parent[nr][nc] = r * C + c;
heap.add(new int[] {ne, nr * C + nc});
}
}
}
LinkedList<Integer> route = new LinkedList<>();
for (int cell = (R - 1) * C + C - 1; cell != -1; cell = parent[cell / C][cell % C])
route.addFirst(heights[cell / C][cell % C]);
StringJoiner s = new StringJoiner(" ");
for (int h : route) s.add(String.valueOf(h));
System.out.println("the least effort, corner to corner: " + best[R - 1][C - 1] + " | by the heights " + s);
}
}
// the least effort, corner to corner: 3 | by the heights 4 7 5 3 2#include <bits/stdc++.h>
using namespace std;
int main() {
vector<vector<int>> heights = {{4, 8, 6}, {7, 1, 9}, {5, 3, 2}}; // a route costs its largest climb or drop
int R = heights.size(), C = heights[0].size();
vector<vector<int>> best(R, vector<int>(C, INT_MAX)), parent(R, vector<int>(C, -1));
best[0][0] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap; // {effort, cell r * C + c}
heap.push({0, 0});
const int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!heap.empty()) {
auto [e, cell] = heap.top();
heap.pop();
int r = cell / C, c = cell % C;
if (e > best[r][c]) continue;
if (r == R - 1 && c == C - 1) break;
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
int ne = max(e, abs(heights[nr][nc] - heights[r][c])); // max in place of +: never smaller than e
if (ne < best[nr][nc]) {
best[nr][nc] = ne;
parent[nr][nc] = cell;
heap.push({ne, nr * C + nc});
}
}
}
vector<int> route;
for (int cell = (R - 1) * C + C - 1; cell != -1; cell = parent[cell / C][cell % C])
route.push_back(heights[cell / C][cell % C]);
reverse(route.begin(), route.end());
cout << "the least effort, corner to corner: " << best[R - 1][C - 1] << " | by the heights";
for (int h : route) cout << " " << h;
cout << "\n";
}
// the least effort, corner to corner: 3 | by the heights 4 7 5 3 2class Heap { // a min-heap of arrays, compared item by item
constructor() { this.a = []; }
get size() { return this.a.length; }
less(i, j) {
const x = this.a[i], y = this.a[j];
for (let k = 0; k < x.length; k++) if (x[k] !== y[k]) return x[k] < y[k];
return false;
}
push(item) {
const a = this.a;
a.push(item);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length) {
a[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(l, m)) m = l;
if (r < a.length && this.less(r, m)) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
const heights = [[4, 8, 6], [7, 1, 9], [5, 3, 2]]; // Path With Minimum Effort: a route costs its largest step
const R = heights.length, C = heights[0].length;
const best = Array.from({ length: R }, () => new Array(C).fill(Infinity));
const parent = Array.from({ length: R }, () => new Array(C).fill(-1));
best[0][0] = 0;
const heap = new Heap();
heap.push([0, 0]); // [effort, cell r * C + c]
while (heap.size) {
const [e, cell] = heap.pop();
const r = Math.floor(cell / C), c = cell % C;
if (e > best[r][c]) continue;
if (r === R - 1 && c === C - 1) break;
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
const ne = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c])); // max in place of +
if (ne < best[nr][nc]) {
best[nr][nc] = ne;
parent[nr][nc] = cell;
heap.push([ne, nr * C + nc]);
}
}
}
const route = [];
for (let cell = (R - 1) * C + C - 1; cell !== -1; cell = parent[Math.floor(cell / C)][cell % C])
route.unshift(heights[Math.floor(cell / C)][cell % C]);
console.log(`the least effort, corner to corner: ${best[R - 1][C - 1]} | by the heights ${route.join(" ")}`);
// the least effort, corner to corner: 3 | by the heights 4 7 5 3 2class Heap { // a min-heap of arrays, compared item by item
private a: number[][] = [];
get size(): number { return this.a.length; }
private less(i: number, j: number): boolean {
const x = this.a[i], y = this.a[j];
for (let k = 0; k < x.length; k++) if (x[k] !== y[k]) return x[k] < y[k];
return false;
}
push(item: number[]): void {
const a = this.a;
a.push(item);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop(): number[] {
const a = this.a, top = a[0], last = a.pop()!;
if (a.length) {
a[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(l, m)) m = l;
if (r < a.length && this.less(r, m)) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
const heights: number[][] = [[4, 8, 6], [7, 1, 9], [5, 3, 2]]; // a route costs its largest climb or drop
const R = heights.length, C = heights[0].length;
const best: number[][] = Array.from({ length: R }, () => new Array(C).fill(Infinity));
const parent: number[][] = Array.from({ length: R }, () => new Array(C).fill(-1));
best[0][0] = 0;
const heap = new Heap();
heap.push([0, 0]); // [effort, cell r * C + c]
while (heap.size) {
const [e, cell] = heap.pop();
const r = Math.floor(cell / C), c = cell % C;
if (e > best[r][c]) continue;
if (r === R - 1 && c === C - 1) break;
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
const ne = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c])); // max in place of +
if (ne < best[nr][nc]) {
best[nr][nc] = ne;
parent[nr][nc] = cell;
heap.push([ne, nr * C + nc]);
}
}
}
const route: number[] = [];
for (let cell = (R - 1) * C + C - 1; cell !== -1; cell = parent[Math.floor(cell / C)][cell % C])
route.unshift(heights[Math.floor(cell / C)][cell % C]);
console.log(`the least effort, corner to corner: ${best[R - 1][C - 1]} | by the heights ${route.join(" ")}`);
// the least effort, corner to corner: 3 | by the heights 4 7 5 3 2using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[,] heights = { {4, 8, 6}, {7, 1, 9}, {5, 3, 2} }; // Path With Minimum Effort: a route costs its largest step
int R = heights.GetLength(0), C = heights.GetLength(1);
var best = new int[R, C];
var parent = new int[R, C];
for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) best[r, c] = int.MaxValue;
best[0, 0] = 0;
parent[0, 0] = -1;
var heap = new PriorityQueue<int, (int, int)>(); // a cell r * C + c, ordered by (effort, cell)
heap.Enqueue(0, (0, 0));
int[][] dirs = { new[] {1, 0}, new[] {-1, 0}, new[] {0, 1}, new[] {0, -1} };
while (heap.TryDequeue(out int cell, out var key)) {
int e = key.Item1, r = cell / C, c = cell % C;
if (e > best[r, c]) continue;
if (r == R - 1 && c == C - 1) break;
foreach (var d in dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
int ne = Math.Max(e, Math.Abs(heights[nr, nc] - heights[r, c])); // max in place of +
if (ne < best[nr, nc]) {
best[nr, nc] = ne;
parent[nr, nc] = cell;
heap.Enqueue(nr * C + nc, (ne, nr * C + nc));
}
}
}
var route = new List<int>();
for (int cell = (R - 1) * C + C - 1; cell != -1; cell = parent[cell / C, cell % C])
route.Insert(0, heights[cell / C, cell % C]);
Console.WriteLine($"the least effort, corner to corner: {best[R - 1, C - 1]} | by the heights {string.Join(" ", route)}");
}
}
// the least effort, corner to corner: 3 | by the heights 4 7 5 3 2package main
import (
"container/heap"
"fmt"
"math"
"strconv"
"strings"
)
type item struct{ d, v int }
type minHeap []item // the smallest distance on top, the smaller vertex first on a tie
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].d < h[j].d || (h[i].d == h[j].d && h[i].v < h[j].v) }
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func main() {
heights := [][]int{{4, 8, 6}, {7, 1, 9}, {5, 3, 2}} // Path With Minimum Effort: a route costs its largest step
R, C := len(heights), len(heights[0])
best, parent := make([][]int, R), make([][]int, R)
for r := range best {
best[r], parent[r] = make([]int, C), make([]int, C)
for c := range best[r] {
best[r][c] = math.MaxInt64
}
}
best[0][0], parent[0][0] = 0, -1
h := &minHeap{{0, 0}} // {effort, cell r * C + c}
dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for h.Len() > 0 {
top := heap.Pop(h).(item)
r, c := top.v/C, top.v%C
if top.d > best[r][c] {
continue
}
if r == R-1 && c == C-1 {
break
}
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= R || nc < 0 || nc >= C {
continue
}
ne := top.d // max in place of +: never smaller than the effort so far
if step := abs(heights[nr][nc] - heights[r][c]); step > ne {
ne = step
}
if ne < best[nr][nc] {
best[nr][nc], parent[nr][nc] = ne, top.v
heap.Push(h, item{ne, nr*C + nc})
}
}
}
route := []string{}
for cell := (R-1)*C + C - 1; cell != -1; cell = parent[cell/C][cell%C] {
route = append([]string{strconv.Itoa(heights[cell/C][cell%C])}, route...)
}
fmt.Printf("the least effort, corner to corner: %d | by the heights %s\n", best[R-1][C-1], strings.Join(route, " "))
}
// the least effort, corner to corner: 3 | by the heights 4 7 5 3 2The route 4, 7, 5, 3, 2 climbs or drops by 3, 2, 2 and 1. Every route leaves 4 by a step of at least 3, to 7 or to 8, so 3 is the least effort there is. The same largest-step idea comes back in Swim in Rising Water, in Union-Find and Minimum Spanning Trees.
Counting the shortest paths
Number of Ways to Arrive at Destination counts the shortest routes. Keep a count beside each distance: a strictly shorter way replaces the count with the count of the vertex it came through, and an equally short way adds that count. Since vertices are settled nearest first, a vertex's count is complete before anything relaxes through it:
import heapq
MOD = 10 ** 9 + 7
def count_ways(n, roads): # Number of Ways to Arrive at Destination: two-way roads [u, v, time]
adj = [[] for _ in range(n)]
for u, v, t in roads:
adj[u].append((v, t))
adj[v].append((u, t))
dist, ways = [float("inf")] * n, [0] * n
dist[0], ways[0] = 0, 1
heap = [(0, 0)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, t in adj[u]:
if d + t < dist[v]: # a shorter way: the old ways no longer count
dist[v], ways[v] = d + t, ways[u]
heapq.heappush(heap, (dist[v], v))
elif d + t == dist[v]: # as short: u's ways are more ways to v
ways[v] = (ways[v] + ways[u]) % MOD
return dist[n - 1], ways[n - 1]
best, ways = count_ways(5, [[0, 1, 2], [0, 2, 3], [1, 3, 2], [2, 3, 1], [3, 4, 2], [1, 4, 5], [0, 4, 6]])
print(f"the shortest time to 4: {best}, reached {ways} ways")
# the shortest time to 4: 6, reached 3 waysimport java.util.*;
public class Main {
public static void main(String[] args) {
int n = 5; // Number of Ways to Arrive at Destination: two-way roads
int[][] roads = {{0, 1, 2}, {0, 2, 3}, {1, 3, 2}, {2, 3, 1}, {3, 4, 2}, {1, 4, 5}, {0, 4, 6}};
final long MOD = 1_000_000_007L;
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] r : roads) {
adj.get(r[0]).add(new int[] {r[1], r[2]});
adj.get(r[1]).add(new int[] {r[0], r[2]});
}
long[] dist = new long[n], ways = new long[n];
Arrays.fill(dist, Long.MAX_VALUE);
dist[0] = 0;
ways[0] = 1;
PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0])
: Long.compare(a[1], b[1]));
heap.add(new long[] {0, 0});
while (!heap.isEmpty()) {
long[] top = heap.poll();
long d = top[0];
int u = (int) top[1];
if (d > dist[u]) continue;
for (int[] e : adj.get(u)) {
int v = e[0];
if (d + e[1] < dist[v]) { // a shorter way: the old ways no longer count
dist[v] = d + e[1];
ways[v] = ways[u];
heap.add(new long[] {dist[v], v});
} else if (d + e[1] == dist[v]) { // as short: u's ways are more ways to v
ways[v] = (ways[v] + ways[u]) % MOD;
}
}
}
System.out.println("the shortest time to 4: " + dist[n - 1] + ", reached " + ways[n - 1] + " ways");
}
}
// the shortest time to 4: 6, reached 3 ways#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 5; // Number of Ways to Arrive at Destination: two-way roads
vector<array<int, 3>> roads = {{0, 1, 2}, {0, 2, 3}, {1, 3, 2}, {2, 3, 1}, {3, 4, 2}, {1, 4, 5}, {0, 4, 6}};
const long long MOD = 1000000007LL;
vector<vector<pair<int, int>>> adj(n);
for (auto& r : roads) {
adj[r[0]].push_back({r[1], r[2]});
adj[r[1]].push_back({r[0], r[2]});
}
vector<long long> dist(n, LLONG_MAX), ways(n, 0);
dist[0] = 0;
ways[0] = 1;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> heap;
heap.push({0, 0});
while (!heap.empty()) {
auto [d, u] = heap.top();
heap.pop();
if (d > dist[u]) continue;
for (auto [v, t] : adj[u]) {
if (d + t < dist[v]) { // a shorter way: the old ways no longer count
dist[v] = d + t;
ways[v] = ways[u];
heap.push({dist[v], v});
} else if (d + t == dist[v]) { // as short: u's ways are more ways to v
ways[v] = (ways[v] + ways[u]) % MOD;
}
}
}
cout << "the shortest time to 4: " << dist[n - 1] << ", reached " << ways[n - 1] << " ways\n";
}
// the shortest time to 4: 6, reached 3 waysclass Heap { // a min-heap of arrays, compared item by item
constructor() { this.a = []; }
get size() { return this.a.length; }
less(i, j) {
const x = this.a[i], y = this.a[j];
for (let k = 0; k < x.length; k++) if (x[k] !== y[k]) return x[k] < y[k];
return false;
}
push(item) {
const a = this.a;
a.push(item);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length) {
a[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(l, m)) m = l;
if (r < a.length && this.less(r, m)) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
const n = 5; // Number of Ways to Arrive at Destination: two-way roads [u, v, time]
const roads = [[0, 1, 2], [0, 2, 3], [1, 3, 2], [2, 3, 1], [3, 4, 2], [1, 4, 5], [0, 4, 6]];
const MOD = 1000000007;
const adj = Array.from({ length: n }, () => []);
for (const [u, v, t] of roads) {
adj[u].push([v, t]);
adj[v].push([u, t]);
}
const dist = new Array(n).fill(Infinity), ways = new Array(n).fill(0);
dist[0] = 0;
ways[0] = 1;
const heap = new Heap();
heap.push([0, 0]);
while (heap.size) {
const [d, u] = heap.pop();
if (d > dist[u]) continue;
for (const [v, t] of adj[u]) {
if (d + t < dist[v]) { // a shorter way: the old ways no longer count
dist[v] = d + t;
ways[v] = ways[u];
heap.push([dist[v], v]);
} else if (d + t === dist[v]) { // as short: u's ways are more ways to v
ways[v] = (ways[v] + ways[u]) % MOD;
}
}
}
console.log(`the shortest time to 4: ${dist[n - 1]}, reached ${ways[n - 1]} ways`);
// the shortest time to 4: 6, reached 3 waysclass Heap { // a min-heap of arrays, compared item by item
private a: number[][] = [];
get size(): number { return this.a.length; }
private less(i: number, j: number): boolean {
const x = this.a[i], y = this.a[j];
for (let k = 0; k < x.length; k++) if (x[k] !== y[k]) return x[k] < y[k];
return false;
}
push(item: number[]): void {
const a = this.a;
a.push(item);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop(): number[] {
const a = this.a, top = a[0], last = a.pop()!;
if (a.length) {
a[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(l, m)) m = l;
if (r < a.length && this.less(r, m)) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
const n = 5; // Number of Ways to Arrive at Destination: two-way roads [u, v, time]
const roads: [number, number, number][] = [[0, 1, 2], [0, 2, 3], [1, 3, 2], [2, 3, 1], [3, 4, 2], [1, 4, 5], [0, 4, 6]];
const MOD = 1000000007;
const adj: [number, number][][] = Array.from({ length: n }, () => []);
for (const [u, v, t] of roads) {
adj[u].push([v, t]);
adj[v].push([u, t]);
}
const dist: number[] = new Array(n).fill(Infinity), ways: number[] = new Array(n).fill(0);
dist[0] = 0;
ways[0] = 1;
const heap = new Heap();
heap.push([0, 0]);
while (heap.size) {
const [d, u] = heap.pop();
if (d > dist[u]) continue;
for (const [v, t] of adj[u]) {
if (d + t < dist[v]) { // a shorter way: the old ways no longer count
dist[v] = d + t;
ways[v] = ways[u];
heap.push([dist[v], v]);
} else if (d + t === dist[v]) { // as short: u's ways are more ways to v
ways[v] = (ways[v] + ways[u]) % MOD;
}
}
}
console.log(`the shortest time to 4: ${dist[n - 1]}, reached ${ways[n - 1]} ways`);
// the shortest time to 4: 6, reached 3 waysusing System;
using System.Collections.Generic;
class Program {
static void Main() {
int n = 5; // Number of Ways to Arrive at Destination: two-way roads
int[][] roads = { new[] {0, 1, 2}, new[] {0, 2, 3}, new[] {1, 3, 2}, new[] {2, 3, 1}, new[] {3, 4, 2},
new[] {1, 4, 5}, new[] {0, 4, 6} };
const long MOD = 1_000_000_007L;
var adj = new List<(int v, int t)>[n];
for (int i = 0; i < n; i++) adj[i] = new List<(int, int)>();
foreach (var r in roads) {
adj[r[0]].Add((r[1], r[2]));
adj[r[1]].Add((r[0], r[2]));
}
var dist = new long[n];
var ways = new long[n];
Array.Fill(dist, long.MaxValue);
dist[0] = 0;
ways[0] = 1;
var heap = new PriorityQueue<int, (long, int)>();
heap.Enqueue(0, (0, 0));
while (heap.TryDequeue(out int u, out var key)) {
long d = key.Item1;
if (d > dist[u]) continue;
foreach (var (v, t) in adj[u]) {
if (d + t < dist[v]) { // a shorter way: the old ways no longer count
dist[v] = d + t;
ways[v] = ways[u];
heap.Enqueue(v, (dist[v], v));
} else if (d + t == dist[v]) { // as short: u's ways are more ways to v
ways[v] = (ways[v] + ways[u]) % MOD;
}
}
}
Console.WriteLine($"the shortest time to 4: {dist[n - 1]}, reached {ways[n - 1]} ways");
}
}
// the shortest time to 4: 6, reached 3 wayspackage main
import (
"container/heap"
"fmt"
"math"
)
type item struct{ d, v int }
type minHeap []item // the smallest distance on top, the smaller vertex first on a tie
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].d < h[j].d || (h[i].d == h[j].d && h[i].v < h[j].v) }
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func main() {
n := 5 // Number of Ways to Arrive at Destination: two-way roads {u, v, time}
roads := [][3]int{{0, 1, 2}, {0, 2, 3}, {1, 3, 2}, {2, 3, 1}, {3, 4, 2}, {1, 4, 5}, {0, 4, 6}}
const MOD = 1000000007
adj := make([][][2]int, n)
for _, r := range roads {
adj[r[0]] = append(adj[r[0]], [2]int{r[1], r[2]})
adj[r[1]] = append(adj[r[1]], [2]int{r[0], r[2]})
}
dist, ways := make([]int, n), make([]int, n)
for i := range dist {
dist[i] = math.MaxInt64
}
dist[0], ways[0] = 0, 1
h := &minHeap{{0, 0}}
for h.Len() > 0 {
top := heap.Pop(h).(item)
if top.d > dist[top.v] {
continue
}
for _, e := range adj[top.v] {
v, t := e[0], e[1]
if top.d+t < dist[v] { // a shorter way: the old ways no longer count
dist[v], ways[v] = top.d+t, ways[top.v]
heap.Push(h, item{dist[v], v})
} else if top.d+t == dist[v] { // as short: u's ways are more ways to v
ways[v] = (ways[v] + ways[top.v]) % MOD
}
}
}
fmt.Printf("the shortest time to 4: %d, reached %d ways\n", dist[n-1], ways[n-1])
}
// the shortest time to 4: 6, reached 3 waysThree routes take 6: 0 → 1 → 3 → 4, 0 → 2 → 3 → 4, and the road 0 → 4 itself. The counts are kept modulo 10⁹ + 7, as the problem asks, because on a big graph they grow past any integer.
Bellman-Ford: every edge, round after round
A shortest path with no cycle has at most n − 1 edges, and each round of relaxing every edge makes sure of one more edge of it. So n − 1 rounds get every distance right, whatever the weights, unless a cycle of negative total weight can be reached. Then going round it once more always lowers something, so one more round still finds a change:
def bellman_ford(n, edges, src): # n - 1 rounds of every edge, then one more to look for a negative cycle
dist = [float("inf")] * n
dist[src] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
cycle = any(dist[u] + w < dist[v] for u, v, w in edges) # still lowering after n - 1 rounds
return dist, cycle
edges = [(0, 1, 6), (0, 2, 7), (1, 2, 8), (1, 3, 5), (2, 3, -3), (3, 1, -2), (2, 4, 9), (4, 3, 7)]
dist, cycle = bellman_ford(5, edges, 0)
print("from 0:", " ".join(map(str, dist)), "| a negative cycle:", "yes" if cycle else "no")
dist, cycle = bellman_ford(5, edges + [(3, 2, -1)], 0)
print("with 3 -> 2 of -1 added, a negative cycle:", "yes" if cycle else "no")
# from 0: 0 2 7 4 16 | a negative cycle: no
# with 3 -> 2 of -1 added, a negative cycle: yesimport java.util.*;
public class Main {
static long[] dist;
static boolean bellmanFord(int n, int[][] edges, int src) { // n - 1 rounds of every edge, then one more
dist = new long[n];
Arrays.fill(dist, Long.MAX_VALUE);
dist[src] = 0;
for (int round = 0; round < n - 1; round++)
for (int[] e : edges)
if (dist[e[0]] != Long.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2];
for (int[] e : edges) // still lowering after n - 1 rounds: a negative cycle
if (dist[e[0]] != Long.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) return true;
return false;
}
public static void main(String[] args) {
int[][] edges = {{0, 1, 6}, {0, 2, 7}, {1, 2, 8}, {1, 3, 5}, {2, 3, -3}, {3, 1, -2}, {2, 4, 9}, {4, 3, 7}};
boolean cycle = bellmanFord(5, edges, 0);
StringJoiner s = new StringJoiner(" ");
for (long d : dist) s.add(String.valueOf(d));
System.out.println("from 0: " + s + " | a negative cycle: " + (cycle ? "yes" : "no"));
int[][] more = Arrays.copyOf(edges, edges.length + 1);
more[edges.length] = new int[] {3, 2, -1};
System.out.println("with 3 -> 2 of -1 added, a negative cycle: " + (bellmanFord(5, more, 0) ? "yes" : "no"));
}
}
// from 0: 0 2 7 4 16 | a negative cycle: no
// with 3 -> 2 of -1 added, a negative cycle: yes#include <bits/stdc++.h>
using namespace std;
vector<long long> dist;
bool bellmanFord(int n, const vector<array<int, 3>>& edges, int src) { // n - 1 rounds of every edge, then one more
dist.assign(n, LLONG_MAX);
dist[src] = 0;
for (int round = 0; round < n - 1; round++)
for (auto& e : edges)
if (dist[e[0]] != LLONG_MAX && dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2];
for (auto& e : edges) // still lowering after n - 1 rounds: a negative cycle
if (dist[e[0]] != LLONG_MAX && dist[e[0]] + e[2] < dist[e[1]]) return true;
return false;
}
int main() {
vector<array<int, 3>> edges = {{0, 1, 6}, {0, 2, 7}, {1, 2, 8}, {1, 3, 5}, {2, 3, -3}, {3, 1, -2}, {2, 4, 9}, {4, 3, 7}};
bool cycle = bellmanFord(5, edges, 0);
cout << "from 0:";
for (long long d : dist) cout << " " << d;
cout << " | a negative cycle: " << (cycle ? "yes" : "no") << "\n";
auto more = edges;
more.push_back({3, 2, -1});
cout << "with 3 -> 2 of -1 added, a negative cycle: " << (bellmanFord(5, more, 0) ? "yes" : "no") << "\n";
}
// from 0: 0 2 7 4 16 | a negative cycle: no
// with 3 -> 2 of -1 added, a negative cycle: yesfunction bellmanFord(n, edges, src) { // n - 1 rounds of every edge, then one more to look for a negative cycle
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
for (let round = 0; round < n - 1; round++)
for (const [u, v, w] of edges) if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
const cycle = edges.some(([u, v, w]) => dist[u] + w < dist[v]); // still lowering after n - 1 rounds
return { dist, cycle };
}
const edges = [[0, 1, 6], [0, 2, 7], [1, 2, 8], [1, 3, 5], [2, 3, -3], [3, 1, -2], [2, 4, 9], [4, 3, 7]];
const first = bellmanFord(5, edges, 0);
console.log(`from 0: ${first.dist.join(" ")} | a negative cycle: ${first.cycle ? "yes" : "no"}`);
const second = bellmanFord(5, [...edges, [3, 2, -1]], 0);
console.log(`with 3 -> 2 of -1 added, a negative cycle: ${second.cycle ? "yes" : "no"}`);
// from 0: 0 2 7 4 16 | a negative cycle: no
// with 3 -> 2 of -1 added, a negative cycle: yesfunction bellmanFord(n: number, edges: [number, number, number][], src: number): { dist: number[]; cycle: boolean } {
const dist: number[] = new Array(n).fill(Infinity); // n - 1 rounds of every edge, then one more
dist[src] = 0;
for (let round = 0; round < n - 1; round++)
for (const [u, v, w] of edges) if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
const cycle = edges.some(([u, v, w]) => dist[u] + w < dist[v]); // still lowering after n - 1 rounds
return { dist, cycle };
}
const edges: [number, number, number][] = [[0, 1, 6], [0, 2, 7], [1, 2, 8], [1, 3, 5], [2, 3, -3], [3, 1, -2],
[2, 4, 9], [4, 3, 7]];
const first = bellmanFord(5, edges, 0);
console.log(`from 0: ${first.dist.join(" ")} | a negative cycle: ${first.cycle ? "yes" : "no"}`);
const second = bellmanFord(5, [...edges, [3, 2, -1]], 0);
console.log(`with 3 -> 2 of -1 added, a negative cycle: ${second.cycle ? "yes" : "no"}`);
// from 0: 0 2 7 4 16 | a negative cycle: no
// with 3 -> 2 of -1 added, a negative cycle: yesusing System;
using System.Linq;
class Program {
static long[] dist;
static bool BellmanFord(int n, int[][] edges, int src) { // n - 1 rounds of every edge, then one more
dist = new long[n];
Array.Fill(dist, long.MaxValue);
dist[src] = 0;
for (int round = 0; round < n - 1; round++)
foreach (var e in edges)
if (dist[e[0]] != long.MaxValue && dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2];
return edges.Any(e => dist[e[0]] != long.MaxValue && dist[e[0]] + e[2] < dist[e[1]]); // still lowering
}
static void Main() {
int[][] edges = { new[] {0, 1, 6}, new[] {0, 2, 7}, new[] {1, 2, 8}, new[] {1, 3, 5}, new[] {2, 3, -3},
new[] {3, 1, -2}, new[] {2, 4, 9}, new[] {4, 3, 7} };
bool cycle = BellmanFord(5, edges, 0);
Console.WriteLine($"from 0: {string.Join(" ", dist)} | a negative cycle: {(cycle ? "yes" : "no")}");
var more = edges.Append(new[] {3, 2, -1}).ToArray();
Console.WriteLine($"with 3 -> 2 of -1 added, a negative cycle: {(BellmanFord(5, more, 0) ? "yes" : "no")}");
}
}
// from 0: 0 2 7 4 16 | a negative cycle: no
// with 3 -> 2 of -1 added, a negative cycle: yespackage main
import (
"fmt"
"math"
"strconv"
"strings"
)
func bellmanFord(n int, edges [][3]int, src int) ([]int, bool) { // n - 1 rounds of every edge, then one more
dist := make([]int, n)
for i := range dist {
dist[i] = math.MaxInt64
}
dist[src] = 0
for round := 0; round < n-1; round++ {
for _, e := range edges {
if dist[e[0]] != math.MaxInt64 && dist[e[0]]+e[2] < dist[e[1]] {
dist[e[1]] = dist[e[0]] + e[2]
}
}
}
for _, e := range edges { // still lowering after n - 1 rounds: a negative cycle
if dist[e[0]] != math.MaxInt64 && dist[e[0]]+e[2] < dist[e[1]] {
return dist, true
}
}
return dist, false
}
func word(yes bool) string {
if yes {
return "yes"
}
return "no"
}
func main() {
edges := [][3]int{{0, 1, 6}, {0, 2, 7}, {1, 2, 8}, {1, 3, 5}, {2, 3, -3}, {3, 1, -2}, {2, 4, 9}, {4, 3, 7}}
dist, cycle := bellmanFord(5, edges, 0)
parts := []string{}
for _, d := range dist {
parts = append(parts, strconv.Itoa(d))
}
fmt.Printf("from 0: %s | a negative cycle: %s\n", strings.Join(parts, " "), word(cycle))
more := append(append([][3]int{}, edges...), [3]int{3, 2, -1})
_, cycle = bellmanFord(5, more, 0)
fmt.Println("with 3 -> 2 of -1 added, a negative cycle:", word(cycle))
}
// from 0: 0 2 7 4 16 | a negative cycle: no
// with 3 -> 2 of -1 added, a negative cycle: yesWith the negative edges 2 → 3 and 3 → 1, the distances settle at 0 2 7 4 16, and a further round changes nothing. Add 3 → 2 of −1, and 2 → 3 → 2 sums to −4: a further round still lowers a distance, so there's no shortest path at all. Bellman-Ford Algorithm is this, in O(V × E).
At most k stops
Cheapest Flights Within K Stops allows at most k stops, so at most k + 1 flights. Bellman-Ford's rounds count flights: after round r, every trip of at most r flights has its price. Run k + 1 rounds, each reading the costs of the round before from a copy, so one round can't string several flights together:
def cheapest(n, flights, src, dst, k): # Cheapest Flights Within K Stops: at most k stops is k + 1 flights
cost = [float("inf")] * n
cost[src] = 0
for _ in range(k + 1): # round r finds the cheapest trips of at most r flights
before = cost[:] # read last round's costs, so a round adds one flight, not several
for u, v, price in flights:
if before[u] + price < cost[v]:
cost[v] = before[u] + price
return -1 if cost[dst] == float("inf") else cost[dst]
flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 3, 400], [1, 3, 300], [0, 2, 200]]
print(" | ".join(f"k = {k}: {cheapest(4, flights, 0, 3, k)}" for k in range(3)))
# k = 0: 400 | k = 1: 250 | k = 2: 150import java.util.*;
public class Main {
static long cheapest(int n, int[][] flights, int src, int dst, int k) { // at most k stops is k + 1 flights
long[] cost = new long[n];
Arrays.fill(cost, Long.MAX_VALUE);
cost[src] = 0;
for (int round = 0; round <= k; round++) { // round r finds the cheapest trips of at most r flights
long[] before = cost.clone(); // read last round's costs: a round adds one flight, not several
for (int[] f : flights)
if (before[f[0]] != Long.MAX_VALUE && before[f[0]] + f[2] < cost[f[1]]) cost[f[1]] = before[f[0]] + f[2];
}
return cost[dst] == Long.MAX_VALUE ? -1 : cost[dst];
}
public static void main(String[] args) {
int[][] flights = {{0, 1, 50}, {1, 2, 50}, {2, 3, 50}, {0, 3, 400}, {1, 3, 300}, {0, 2, 200}};
StringJoiner s = new StringJoiner(" | ");
for (int k = 0; k <= 2; k++) s.add("k = " + k + ": " + cheapest(4, flights, 0, 3, k));
System.out.println(s);
}
}
// k = 0: 400 | k = 1: 250 | k = 2: 150#include <bits/stdc++.h>
using namespace std;
long long cheapest(int n, const vector<array<int, 3>>& flights, int src, int dst, int k) { // k stops: k + 1 flights
vector<long long> cost(n, LLONG_MAX);
cost[src] = 0;
for (int round = 0; round <= k; round++) { // round r finds the cheapest trips of at most r flights
auto before = cost; // read last round's costs: a round adds one flight, not several
for (auto& f : flights)
if (before[f[0]] != LLONG_MAX && before[f[0]] + f[2] < cost[f[1]]) cost[f[1]] = before[f[0]] + f[2];
}
return cost[dst] == LLONG_MAX ? -1 : cost[dst];
}
int main() {
vector<array<int, 3>> flights = {{0, 1, 50}, {1, 2, 50}, {2, 3, 50}, {0, 3, 400}, {1, 3, 300}, {0, 2, 200}};
for (int k = 0; k <= 2; k++) cout << (k ? " | " : "") << "k = " << k << ": " << cheapest(4, flights, 0, 3, k);
cout << "\n";
}
// k = 0: 400 | k = 1: 250 | k = 2: 150function cheapest(n, flights, src, dst, k) { // Cheapest Flights Within K Stops: k stops is k + 1 flights
const cost = new Array(n).fill(Infinity);
cost[src] = 0;
for (let round = 0; round <= k; round++) { // round r finds the cheapest trips of at most r flights
const before = [...cost]; // read last round's costs, so a round adds one flight, not several
for (const [u, v, price] of flights) if (before[u] + price < cost[v]) cost[v] = before[u] + price;
}
return cost[dst] === Infinity ? -1 : cost[dst];
}
const flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 3, 400], [1, 3, 300], [0, 2, 200]];
console.log([0, 1, 2].map((k) => `k = ${k}: ${cheapest(4, flights, 0, 3, k)}`).join(" | "));
// k = 0: 400 | k = 1: 250 | k = 2: 150function cheapest(n: number, flights: [number, number, number][], src: number, dst: number, k: number): number {
const cost: number[] = new Array(n).fill(Infinity); // Cheapest Flights Within K Stops: k + 1 flights at most
cost[src] = 0;
for (let round = 0; round <= k; round++) { // round r finds the cheapest trips of at most r flights
const before = [...cost]; // read last round's costs, so a round adds one flight, not several
for (const [u, v, price] of flights) if (before[u] + price < cost[v]) cost[v] = before[u] + price;
}
return cost[dst] === Infinity ? -1 : cost[dst];
}
const flights: [number, number, number][] = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 3, 400], [1, 3, 300], [0, 2, 200]];
console.log([0, 1, 2].map((k) => `k = ${k}: ${cheapest(4, flights, 0, 3, k)}`).join(" | "));
// k = 0: 400 | k = 1: 250 | k = 2: 150using System;
using System.Linq;
class Program {
static long Cheapest(int n, int[][] flights, int src, int dst, int k) { // at most k stops is k + 1 flights
var cost = new long[n];
Array.Fill(cost, long.MaxValue);
cost[src] = 0;
for (int round = 0; round <= k; round++) { // round r finds the cheapest trips of at most r flights
var before = (long[]) cost.Clone(); // read last round's costs: a round adds one flight, not several
foreach (var f in flights)
if (before[f[0]] != long.MaxValue && before[f[0]] + f[2] < cost[f[1]]) cost[f[1]] = before[f[0]] + f[2];
}
return cost[dst] == long.MaxValue ? -1 : cost[dst];
}
static void Main() {
int[][] flights = { new[] {0, 1, 50}, new[] {1, 2, 50}, new[] {2, 3, 50}, new[] {0, 3, 400}, new[] {1, 3, 300},
new[] {0, 2, 200} };
Console.WriteLine(string.Join(" | ", Enumerable.Range(0, 3).Select(k => $"k = {k}: {Cheapest(4, flights, 0, 3, k)}")));
}
}
// k = 0: 400 | k = 1: 250 | k = 2: 150package main
import (
"fmt"
"math"
"strings"
)
func cheapest(n int, flights [][3]int, src, dst, k int) int { // at most k stops is k + 1 flights
cost := make([]int, n)
for i := range cost {
cost[i] = math.MaxInt64
}
cost[src] = 0
for round := 0; round <= k; round++ { // round r finds the cheapest trips of at most r flights
before := append([]int{}, cost...) // read last round's costs: a round adds one flight, not several
for _, f := range flights {
if before[f[0]] != math.MaxInt64 && before[f[0]]+f[2] < cost[f[1]] {
cost[f[1]] = before[f[0]] + f[2]
}
}
}
if cost[dst] == math.MaxInt64 {
return -1
}
return cost[dst]
}
func main() {
flights := [][3]int{{0, 1, 50}, {1, 2, 50}, {2, 3, 50}, {0, 3, 400}, {1, 3, 300}, {0, 2, 200}}
parts := []string{}
for k := 0; k <= 2; k++ {
parts = append(parts, fmt.Sprintf("k = %d: %d", k, cheapest(4, flights, 0, 3, k)))
}
fmt.Println(strings.Join(parts, " | "))
}
// k = 0: 400 | k = 1: 250 | k = 2: 150With no stop there's only the direct flight, 400. One stop finds 0 → 2 → 3 for 250, and two stops 0 → 1 → 2 → 3 for 150. Dijkstra on price alone would answer 150 every time: the cheapest route with any number of stops.
A DAG: one pass in order
When the graph is a DAG, there's an order with every edge pointing forward, the topological order of Cycles, Bipartite Graphs and Topological Order. Relax each vertex's edges in that order, once. When a vertex's turn comes, everything leading into it has been relaxed already, so its distance is final, negative edges and all, in O(V + E):
from collections import deque
def dag_shortest(n, edges, src): # Shortest Path in DAG: relax each vertex's edges once, in order
adj, indeg = [[] for _ in range(n)], [0] * n
for u, v, w in edges:
adj[u].append((v, w))
indeg[v] += 1
order, queue = [], deque(u for u in range(n) if indeg[u] == 0)
while queue: # Kahn's algorithm, from Cycles, Bipartite Graphs and Topological Order
u = queue.popleft()
order.append(u)
for v, _ in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
queue.append(v)
dist = [float("inf")] * n
dist[src] = 0
for u in order: # everything before u is done, so dist[u] is final now
if dist[u] != float("inf"):
for v, w in adj[u]:
dist[v] = min(dist[v], dist[u] + w)
return order, dist
edges = [(0, 1, 5), (0, 2, 3), (1, 3, 6), (1, 2, 2), (2, 4, 4), (2, 5, 2), (2, 3, 7), (3, 4, -1), (4, 5, -3)]
order, dist = dag_shortest(6, edges, 0)
print("topological order:", " ".join(map(str, order)), "| from 0:", " ".join(map(str, dist)))
# topological order: 0 1 2 3 4 5 | from 0: 0 5 3 10 7 4import java.util.*;
public class Main {
public static void main(String[] args) {
int n = 6; // Shortest Path in DAG: relax each vertex's edges once, in order
int[][] edges = {{0, 1, 5}, {0, 2, 3}, {1, 3, 6}, {1, 2, 2}, {2, 4, 4}, {2, 5, 2}, {2, 3, 7}, {3, 4, -1}, {4, 5, -3}};
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : edges) {
adj.get(e[0]).add(new int[] {e[1], e[2]});
indeg[e[1]]++;
}
List<Integer> order = new ArrayList<>();
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int u = 0; u < n; u++) if (indeg[u] == 0) queue.add(u);
while (!queue.isEmpty()) { // Kahn's algorithm, from Cycles, Bipartite Graphs and Topological Order
int u = queue.poll();
order.add(u);
for (int[] e : adj.get(u)) if (--indeg[e[0]] == 0) queue.add(e[0]);
}
long[] dist = new long[n];
Arrays.fill(dist, Long.MAX_VALUE);
dist[0] = 0;
for (int u : order) { // everything before u is done, so dist[u] is final now
if (dist[u] == Long.MAX_VALUE) continue;
for (int[] e : adj.get(u)) dist[e[0]] = Math.min(dist[e[0]], dist[u] + e[1]);
}
StringJoiner a = new StringJoiner(" "), b = new StringJoiner(" ");
for (int u : order) a.add(String.valueOf(u));
for (long d : dist) b.add(String.valueOf(d));
System.out.println("topological order: " + a + " | from 0: " + b);
}
}
// topological order: 0 1 2 3 4 5 | from 0: 0 5 3 10 7 4#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 6; // Shortest Path in DAG: relax each vertex's edges once, in order
vector<array<int, 3>> edges = {{0, 1, 5}, {0, 2, 3}, {1, 3, 6}, {1, 2, 2}, {2, 4, 4}, {2, 5, 2}, {2, 3, 7}, {3, 4, -1},
{4, 5, -3}};
vector<vector<pair<int, int>>> adj(n);
vector<int> indeg(n, 0), order;
for (auto& e : edges) {
adj[e[0]].push_back({e[1], e[2]});
indeg[e[1]]++;
}
queue<int> q;
for (int u = 0; u < n; u++) if (indeg[u] == 0) q.push(u);
while (!q.empty()) { // Kahn's algorithm, from Cycles, Bipartite Graphs and Topological Order
int u = q.front();
q.pop();
order.push_back(u);
for (auto [v, w] : adj[u]) if (--indeg[v] == 0) q.push(v);
}
vector<long long> dist(n, LLONG_MAX);
dist[0] = 0;
for (int u : order) { // everything before u is done, so dist[u] is final now
if (dist[u] == LLONG_MAX) continue;
for (auto [v, w] : adj[u]) dist[v] = min(dist[v], dist[u] + w);
}
cout << "topological order:";
for (int u : order) cout << " " << u;
cout << " | from 0:";
for (long long d : dist) cout << " " << d;
cout << "\n";
}
// topological order: 0 1 2 3 4 5 | from 0: 0 5 3 10 7 4function dagShortest(n, edges, src) { // Shortest Path in DAG: relax each vertex's edges once, in order
const adj = Array.from({ length: n }, () => []), indeg = new Array(n).fill(0);
for (const [u, v, w] of edges) {
adj[u].push([v, w]);
indeg[v]++;
}
const order = [];
for (let u = 0; u < n; u++) if (indeg[u] === 0) order.push(u);
for (let head = 0; head < order.length; head++) // Kahn's algorithm: the order is its own queue
for (const [v] of adj[order[head]]) if (--indeg[v] === 0) order.push(v);
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
for (const u of order) { // everything before u is done, so dist[u] is final now
if (dist[u] === Infinity) continue;
for (const [v, w] of adj[u]) dist[v] = Math.min(dist[v], dist[u] + w);
}
return { order, dist };
}
const edges = [[0, 1, 5], [0, 2, 3], [1, 3, 6], [1, 2, 2], [2, 4, 4], [2, 5, 2], [2, 3, 7], [3, 4, -1], [4, 5, -3]];
const { order, dist } = dagShortest(6, edges, 0);
console.log(`topological order: ${order.join(" ")} | from 0: ${dist.join(" ")}`);
// topological order: 0 1 2 3 4 5 | from 0: 0 5 3 10 7 4function dagShortest(n: number, edges: [number, number, number][], src: number): { order: number[]; dist: number[] } {
const adj: [number, number][][] = Array.from({ length: n }, () => []); // relax each vertex's edges once, in order
const indeg = new Array<number>(n).fill(0);
for (const [u, v, w] of edges) {
adj[u].push([v, w]);
indeg[v]++;
}
const order: number[] = [];
for (let u = 0; u < n; u++) if (indeg[u] === 0) order.push(u);
for (let head = 0; head < order.length; head++) // Kahn's algorithm: the order is its own queue
for (const [v] of adj[order[head]]) if (--indeg[v] === 0) order.push(v);
const dist: number[] = new Array(n).fill(Infinity);
dist[src] = 0;
for (const u of order) { // everything before u is done, so dist[u] is final now
if (dist[u] === Infinity) continue;
for (const [v, w] of adj[u]) dist[v] = Math.min(dist[v], dist[u] + w);
}
return { order, dist };
}
const edges: [number, number, number][] = [[0, 1, 5], [0, 2, 3], [1, 3, 6], [1, 2, 2], [2, 4, 4], [2, 5, 2], [2, 3, 7],
[3, 4, -1], [4, 5, -3]];
const { order, dist } = dagShortest(6, edges, 0);
console.log(`topological order: ${order.join(" ")} | from 0: ${dist.join(" ")}`);
// topological order: 0 1 2 3 4 5 | from 0: 0 5 3 10 7 4using System;
using System.Collections.Generic;
class Program {
static void Main() {
int n = 6; // Shortest Path in DAG: relax each vertex's edges once, in order
int[][] edges = { new[] {0, 1, 5}, new[] {0, 2, 3}, new[] {1, 3, 6}, new[] {1, 2, 2}, new[] {2, 4, 4},
new[] {2, 5, 2}, new[] {2, 3, 7}, new[] {3, 4, -1}, new[] {4, 5, -3} };
var adj = new List<(int v, int w)>[n];
for (int i = 0; i < n; i++) adj[i] = new List<(int, int)>();
var indeg = new int[n];
foreach (var e in edges) {
adj[e[0]].Add((e[1], e[2]));
indeg[e[1]]++;
}
var order = new List<int>();
var queue = new Queue<int>();
for (int u = 0; u < n; u++) if (indeg[u] == 0) queue.Enqueue(u);
while (queue.Count > 0) { // Kahn's algorithm, from Cycles, Bipartite Graphs and Topological Order
int u = queue.Dequeue();
order.Add(u);
foreach (var (v, _) in adj[u]) if (--indeg[v] == 0) queue.Enqueue(v);
}
var dist = new long[n];
Array.Fill(dist, long.MaxValue);
dist[0] = 0;
foreach (int u in order) { // everything before u is done, so dist[u] is final now
if (dist[u] == long.MaxValue) continue;
foreach (var (v, w) in adj[u]) dist[v] = Math.Min(dist[v], dist[u] + w);
}
Console.WriteLine($"topological order: {string.Join(" ", order)} | from 0: {string.Join(" ", dist)}");
}
}
// topological order: 0 1 2 3 4 5 | from 0: 0 5 3 10 7 4package main
import (
"fmt"
"math"
"strconv"
"strings"
)
func joined(xs []int) string {
parts := make([]string, len(xs))
for i, x := range xs {
parts[i] = strconv.Itoa(x)
}
return strings.Join(parts, " ")
}
func main() {
n := 6 // Shortest Path in DAG: relax each vertex's edges once, in order
edges := [][3]int{{0, 1, 5}, {0, 2, 3}, {1, 3, 6}, {1, 2, 2}, {2, 4, 4}, {2, 5, 2}, {2, 3, 7}, {3, 4, -1}, {4, 5, -3}}
adj := make([][][2]int, n)
indeg := make([]int, n)
for _, e := range edges {
adj[e[0]] = append(adj[e[0]], [2]int{e[1], e[2]})
indeg[e[1]]++
}
order := []int{}
for u := 0; u < n; u++ {
if indeg[u] == 0 {
order = append(order, u)
}
}
for head := 0; head < len(order); head++ { // Kahn's algorithm: the order is its own queue
for _, e := range adj[order[head]] {
indeg[e[0]]--
if indeg[e[0]] == 0 {
order = append(order, e[0])
}
}
}
dist := make([]int, n)
for i := range dist {
dist[i] = math.MaxInt64
}
dist[0] = 0
for _, u := range order { // everything before u is done, so dist[u] is final now
if dist[u] == math.MaxInt64 {
continue
}
for _, e := range adj[u] {
if dist[u]+e[1] < dist[e[0]] {
dist[e[0]] = dist[u] + e[1]
}
}
}
fmt.Printf("topological order: %s | from 0: %s\n", joined(order), joined(dist))
}
// topological order: 0 1 2 3 4 5 | from 0: 0 5 3 10 7 45 is reached for 4: 0 → 2 → 4 costs 7, and the edge 4 → 5 of −3 brings it to 4, cheaper than the edge 2 → 5, which gives 5. Shortest Path in DAG is this.
Floyd-Warshall: every pair
For the distance between every pair, Floyd-Warshall grows the set of vertices a path may pass through, one at a time: after round k, d[i][j] is the shortest way from i to j through any of 0 to k. Passing through k as well means d[i][k] + d[k][j], two distances already known for the smaller set. Three loops, k outermost, O(n³):
def floyd_warshall(n, edges): # every pair at once; a two-way road [u, v, w]
INF = float("inf")
d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
for u, v, w in edges:
d[u][v] = d[v][u] = min(d[u][v], w)
for k in range(n): # after round k, d[i][j] may pass through any of 0..k on the way
for i in range(n):
for j in range(n):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
return d
n, threshold = 5, 6
d = floyd_warshall(n, [(0, 1, 3), (1, 2, 4), (0, 3, 9), (2, 3, 1), (3, 4, 2), (1, 4, 8)])
for row in d:
print(" ".join(map(str, row)))
near = [sum(1 for j in range(n) if j != i and d[i][j] <= threshold) for i in range(n)]
city = 0
for i in range(n): # the fewest within reach; on a tie, the larger number
if near[i] <= near[city]:
city = i
print(f"within {threshold}:", " ".join(map(str, near)), "| the city:", city)
# 0 3 7 8 10
# 3 0 4 5 7
# 7 4 0 1 3
# 8 5 1 0 2
# 10 7 3 2 0
# within 6: 1 3 3 3 2 | the city: 0import java.util.*;
public class Main {
public static void main(String[] args) {
int n = 5, threshold = 6; // every pair at once; two-way roads {u, v, w}
int[][] edges = {{0, 1, 3}, {1, 2, 4}, {0, 3, 9}, {2, 3, 1}, {3, 4, 2}, {1, 4, 8}};
final long INF = Long.MAX_VALUE / 4;
long[][] d = new long[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(d[i], INF);
d[i][i] = 0;
}
for (int[] e : edges) d[e[0]][e[1]] = d[e[1]][e[0]] = Math.min(d[e[0]][e[1]], e[2]);
for (int k = 0; k < n; k++) // after round k, d[i][j] may pass through any of 0..k
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
for (long[] row : d) {
StringJoiner s = new StringJoiner(" ");
for (long x : row) s.add(String.valueOf(x));
System.out.println(s);
}
int[] near = new int[n];
int city = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) if (j != i && d[i][j] <= threshold) near[i]++;
}
for (int i = 0; i < n; i++) if (near[i] <= near[city]) city = i; // the fewest; on a tie, the larger number
StringJoiner s = new StringJoiner(" ");
for (int x : near) s.add(String.valueOf(x));
System.out.println("within " + threshold + ": " + s + " | the city: " + city);
}
}
// 0 3 7 8 10
// 3 0 4 5 7
// 7 4 0 1 3
// 8 5 1 0 2
// 10 7 3 2 0
// within 6: 1 3 3 3 2 | the city: 0#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 5, threshold = 6; // every pair at once; two-way roads {u, v, w}
vector<array<int, 3>> edges = {{0, 1, 3}, {1, 2, 4}, {0, 3, 9}, {2, 3, 1}, {3, 4, 2}, {1, 4, 8}};
const long long INF = LLONG_MAX / 4;
vector<vector<long long>> d(n, vector<long long>(n, INF));
for (int i = 0; i < n; i++) d[i][i] = 0;
for (auto& e : edges) d[e[0]][e[1]] = d[e[1]][e[0]] = min<long long>(d[e[0]][e[1]], e[2]);
for (int k = 0; k < n; k++) // after round k, d[i][j] may pass through any of 0..k
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
for (auto& row : d) {
for (int j = 0; j < n; j++) cout << (j ? " " : "") << row[j];
cout << "\n";
}
vector<int> near(n, 0);
int city = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) if (j != i && d[i][j] <= threshold) near[i]++;
for (int i = 0; i < n; i++) if (near[i] <= near[city]) city = i; // the fewest; on a tie, the larger number
cout << "within " << threshold << ":";
for (int x : near) cout << " " << x;
cout << " | the city: " << city << "\n";
}
// 0 3 7 8 10
// 3 0 4 5 7
// 7 4 0 1 3
// 8 5 1 0 2
// 10 7 3 2 0
// within 6: 1 3 3 3 2 | the city: 0function floydWarshall(n, edges) { // every pair at once; a two-way road [u, v, w]
const d = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
for (const [u, v, w] of edges) d[u][v] = d[v][u] = Math.min(d[u][v], w);
for (let k = 0; k < n; k++) // after round k, d[i][j] may pass through any of 0..k on the way
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
return d;
}
const n = 5, threshold = 6;
const d = floydWarshall(n, [[0, 1, 3], [1, 2, 4], [0, 3, 9], [2, 3, 1], [3, 4, 2], [1, 4, 8]]);
for (const row of d) console.log(row.join(" "));
const near = d.map((row, i) => row.filter((x, j) => j !== i && x <= threshold).length);
let city = 0;
for (let i = 0; i < n; i++) if (near[i] <= near[city]) city = i; // the fewest; on a tie, the larger number
console.log(`within ${threshold}: ${near.join(" ")} | the city: ${city}`);
// 0 3 7 8 10
// 3 0 4 5 7
// 7 4 0 1 3
// 8 5 1 0 2
// 10 7 3 2 0
// within 6: 1 3 3 3 2 | the city: 0function floydWarshall(n: number, edges: [number, number, number][]): number[][] { // every pair at once
const d: number[][] = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
for (const [u, v, w] of edges) d[u][v] = d[v][u] = Math.min(d[u][v], w); // a two-way road [u, v, w]
for (let k = 0; k < n; k++) // after round k, d[i][j] may pass through any of 0..k on the way
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
return d;
}
const n = 5, threshold = 6;
const d = floydWarshall(n, [[0, 1, 3], [1, 2, 4], [0, 3, 9], [2, 3, 1], [3, 4, 2], [1, 4, 8]]);
for (const row of d) console.log(row.join(" "));
const near = d.map((row, i) => row.filter((x, j) => j !== i && x <= threshold).length);
let city = 0;
for (let i = 0; i < n; i++) if (near[i] <= near[city]) city = i; // the fewest; on a tie, the larger number
console.log(`within ${threshold}: ${near.join(" ")} | the city: ${city}`);
// 0 3 7 8 10
// 3 0 4 5 7
// 7 4 0 1 3
// 8 5 1 0 2
// 10 7 3 2 0
// within 6: 1 3 3 3 2 | the city: 0using System;
using System.Collections.Generic;
class Program {
static void Main() {
int n = 5, threshold = 6; // every pair at once; two-way roads {u, v, w}
int[][] edges = { new[] {0, 1, 3}, new[] {1, 2, 4}, new[] {0, 3, 9}, new[] {2, 3, 1}, new[] {3, 4, 2},
new[] {1, 4, 8} };
const long INF = long.MaxValue / 4;
var d = new long[n, n];
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i, j] = i == j ? 0 : INF;
foreach (var e in edges) d[e[0], e[1]] = d[e[1], e[0]] = Math.Min(d[e[0], e[1]], e[2]);
for (int k = 0; k < n; k++) // after round k, d[i, j] may pass through any of 0..k
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (d[i, k] + d[k, j] < d[i, j]) d[i, j] = d[i, k] + d[k, j];
var near = new int[n];
for (int i = 0; i < n; i++) {
var row = new List<long>();
for (int j = 0; j < n; j++) {
row.Add(d[i, j]);
if (j != i && d[i, j] <= threshold) near[i]++;
}
Console.WriteLine(string.Join(" ", row));
}
int city = 0;
for (int i = 0; i < n; i++) if (near[i] <= near[city]) city = i; // the fewest; on a tie, the larger number
Console.WriteLine($"within {threshold}: {string.Join(" ", near)} | the city: {city}");
}
}
// 0 3 7 8 10
// 3 0 4 5 7
// 7 4 0 1 3
// 8 5 1 0 2
// 10 7 3 2 0
// within 6: 1 3 3 3 2 | the city: 0package main
import (
"fmt"
"math"
"strconv"
"strings"
)
func main() {
n, threshold := 5, 6 // every pair at once; two-way roads {u, v, w}
edges := [][3]int{{0, 1, 3}, {1, 2, 4}, {0, 3, 9}, {2, 3, 1}, {3, 4, 2}, {1, 4, 8}}
INF := math.MaxInt64 / 4
d := make([][]int, n)
for i := range d {
d[i] = make([]int, n)
for j := range d[i] {
if i != j {
d[i][j] = INF
}
}
}
for _, e := range edges {
if e[2] < d[e[0]][e[1]] {
d[e[0]][e[1]], d[e[1]][e[0]] = e[2], e[2]
}
}
for k := 0; k < n; k++ { // after round k, d[i][j] may pass through any of 0..k on the way
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if d[i][k]+d[k][j] < d[i][j] {
d[i][j] = d[i][k] + d[k][j]
}
}
}
}
near := make([]int, n)
for i, row := range d {
parts := []string{}
for j, x := range row {
parts = append(parts, strconv.Itoa(x))
if j != i && x <= threshold {
near[i]++
}
}
fmt.Println(strings.Join(parts, " "))
}
city := 0
for i := 0; i < n; i++ {
if near[i] <= near[city] { // the fewest; on a tie, the larger number
city = i
}
}
parts := []string{}
for _, x := range near {
parts = append(parts, strconv.Itoa(x))
}
fmt.Printf("within %d: %s | the city: %d\n", threshold, strings.Join(parts, " "), city)
}
// 0 3 7 8 10
// 3 0 4 5 7
// 7 4 0 1 3
// 8 5 1 0 2
// 10 7 3 2 0
// within 6: 1 3 3 3 2 | the city: 0Find the City With the Smallest Number of Neighbors at a Threshold Distance reads the matrix. Within 6, city 0 reaches only 1, at 3; cities 1, 2 and 3 reach three others each; city 4 reaches two. So the city is 0; on a tie it would be the larger number. Floyd-Warshall Algorithm asks for the matrix itself. With k innermost instead, a pair is finished before the paths it needs, which Mistakes that look right runs.
Ratios as weights
Evaluate Division gives equations like x / y = 4 and asks for other quotients. Each equation is two edges, x → y weighing 4 and y → x weighing 1/4, and a quotient is the product of the weights along any path between the two: a search, with multiplying where the adding was:
from collections import deque
def calc_equation(equations, values, queries): # Evaluate Division: a / b = x is an edge a -> b of x, b -> a of 1/x
graph = {}
for (a, b), x in zip(equations, values):
graph.setdefault(a, []).append((b, x))
graph.setdefault(b, []).append((a, 1 / x))
answers = []
for s, t in queries:
if s not in graph or t not in graph:
answers.append(-1.0)
continue
seen, queue, found = {s}, deque([(s, 1.0)]), -1.0
while queue: # a path's value is the product of its edges
u, product = queue.popleft()
if u == t:
found = product
break
for v, x in graph[u]:
if v not in seen:
seen.add(v)
queue.append((v, product * x))
answers.append(found)
return answers
queries = [["x", "w"], ["w", "y"], ["y", "x"], ["x", "q"], ["z", "z"]]
answers = calc_equation([["x", "y"], ["y", "z"], ["z", "w"]], [4.0, 0.5, 3.0], queries)
print(" | ".join(f"{s} / {t} = {a:.5f}" for (s, t), a in zip(queries, answers)))
# x / w = 6.00000 | w / y = 0.66667 | y / x = 0.25000 | x / q = -1.00000 | z / z = 1.00000import java.util.*;
public class Main {
static double[] calcEquation(String[][] equations, double[] values, String[][] queries) { // a / b = x
Map<String, Map<String, Double>> graph = new HashMap<>(); // an edge a -> b of x, and b -> a of 1/x
for (int i = 0; i < equations.length; i++) {
String a = equations[i][0], b = equations[i][1];
graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, values[i]);
graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1 / values[i]);
}
double[] answers = new double[queries.length];
for (int q = 0; q < queries.length; q++) {
String s = queries[q][0], t = queries[q][1];
answers[q] = -1.0;
if (!graph.containsKey(s) || !graph.containsKey(t)) continue;
Set<String> seen = new HashSet<>(List.of(s));
ArrayDeque<Object[]> queue = new ArrayDeque<>();
queue.add(new Object[] {s, 1.0});
while (!queue.isEmpty()) { // a path's value is the product of its edges
Object[] top = queue.poll();
String u = (String) top[0];
double product = (Double) top[1];
if (u.equals(t)) {
answers[q] = product;
break;
}
for (Map.Entry<String, Double> e : graph.get(u).entrySet()) {
if (seen.add(e.getKey())) queue.add(new Object[] {e.getKey(), product * e.getValue()});
}
}
}
return answers;
}
public static void main(String[] args) {
String[][] queries = {{"x", "w"}, {"w", "y"}, {"y", "x"}, {"x", "q"}, {"z", "z"}};
double[] answers = calcEquation(new String[][] {{"x", "y"}, {"y", "z"}, {"z", "w"}}, new double[] {4.0, 0.5, 3.0},
queries);
StringJoiner s = new StringJoiner(" | ");
for (int i = 0; i < queries.length; i++)
s.add(queries[i][0] + " / " + queries[i][1] + " = " + String.format(Locale.ROOT, "%.5f", answers[i]));
System.out.println(s);
}
}
// x / w = 6.00000 | w / y = 0.66667 | y / x = 0.25000 | x / q = -1.00000 | z / z = 1.00000#include <bits/stdc++.h>
using namespace std;
vector<double> calcEquation(const vector<pair<string, string>>& equations, const vector<double>& values,
const vector<pair<string, string>>& queries) { // a / b = x: a -> b of x, b -> a of 1/x
map<string, vector<pair<string, double>>> graph;
for (size_t i = 0; i < equations.size(); i++) {
auto& [a, b] = equations[i];
graph[a].push_back({b, values[i]});
graph[b].push_back({a, 1 / values[i]});
}
vector<double> answers;
for (auto& [s, t] : queries) {
double found = -1.0;
if (graph.count(s) && graph.count(t)) {
set<string> seen = {s};
queue<pair<string, double>> q;
q.push({s, 1.0});
while (!q.empty()) { // a path's value is the product of its edges
auto [u, product] = q.front();
q.pop();
if (u == t) {
found = product;
break;
}
for (auto& [v, x] : graph[u])
if (seen.insert(v).second) q.push({v, product * x});
}
}
answers.push_back(found);
}
return answers;
}
int main() {
vector<pair<string, string>> queries = {{"x", "w"}, {"w", "y"}, {"y", "x"}, {"x", "q"}, {"z", "z"}};
auto answers = calcEquation({{"x", "y"}, {"y", "z"}, {"z", "w"}}, {4.0, 0.5, 3.0}, queries);
for (size_t i = 0; i < queries.size(); i++)
printf("%s%s / %s = %.5f", i ? " | " : "", queries[i].first.c_str(), queries[i].second.c_str(), answers[i]);
printf("\n");
}
// x / w = 6.00000 | w / y = 0.66667 | y / x = 0.25000 | x / q = -1.00000 | z / z = 1.00000function calcEquation(equations, values, queries) { // Evaluate Division: a / b = x is a -> b of x, b -> a of 1/x
const graph = new Map();
equations.forEach(([a, b], i) => {
if (!graph.has(a)) graph.set(a, []);
if (!graph.has(b)) graph.set(b, []);
graph.get(a).push([b, values[i]]);
graph.get(b).push([a, 1 / values[i]]);
});
return queries.map(([s, t]) => {
if (!graph.has(s) || !graph.has(t)) return -1.0;
const seen = new Set([s]), queue = [[s, 1.0]];
for (let head = 0; head < queue.length; head++) { // a path's value is the product of its edges
const [u, product] = queue[head];
if (u === t) return product;
for (const [v, x] of graph.get(u)) {
if (!seen.has(v)) {
seen.add(v);
queue.push([v, product * x]);
}
}
}
return -1.0;
});
}
const queries = [["x", "w"], ["w", "y"], ["y", "x"], ["x", "q"], ["z", "z"]];
const answers = calcEquation([["x", "y"], ["y", "z"], ["z", "w"]], [4.0, 0.5, 3.0], queries);
console.log(queries.map(([s, t], i) => `${s} / ${t} = ${answers[i].toFixed(5)}`).join(" | "));
// x / w = 6.00000 | w / y = 0.66667 | y / x = 0.25000 | x / q = -1.00000 | z / z = 1.00000function calcEquation(equations: [string, string][], values: number[], queries: [string, string][]): number[] {
const graph = new Map<string, [string, number][]>(); // a / b = x is an edge a -> b of x, and b -> a of 1/x
equations.forEach(([a, b], i) => {
if (!graph.has(a)) graph.set(a, []);
if (!graph.has(b)) graph.set(b, []);
graph.get(a)!.push([b, values[i]]);
graph.get(b)!.push([a, 1 / values[i]]);
});
return queries.map(([s, t]) => {
if (!graph.has(s) || !graph.has(t)) return -1.0;
const seen = new Set<string>([s]), queue: [string, number][] = [[s, 1.0]];
for (let head = 0; head < queue.length; head++) { // a path's value is the product of its edges
const [u, product] = queue[head];
if (u === t) return product;
for (const [v, x] of graph.get(u)!) {
if (!seen.has(v)) {
seen.add(v);
queue.push([v, product * x]);
}
}
}
return -1.0;
});
}
const queries: [string, string][] = [["x", "w"], ["w", "y"], ["y", "x"], ["x", "q"], ["z", "z"]];
const answers = calcEquation([["x", "y"], ["y", "z"], ["z", "w"]], [4.0, 0.5, 3.0], queries);
console.log(queries.map(([s, t], i) => `${s} / ${t} = ${answers[i].toFixed(5)}`).join(" | "));
// x / w = 6.00000 | w / y = 0.66667 | y / x = 0.25000 | x / q = -1.00000 | z / z = 1.00000using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
class Program {
static double[] CalcEquation(string[][] equations, double[] values, string[][] queries) { // a / b = x
var graph = new Dictionary<string, List<(string v, double x)>>(); // a -> b of x, and b -> a of 1/x
for (int i = 0; i < equations.Length; i++) {
string a = equations[i][0], b = equations[i][1];
if (!graph.ContainsKey(a)) graph[a] = new List<(string, double)>();
if (!graph.ContainsKey(b)) graph[b] = new List<(string, double)>();
graph[a].Add((b, values[i]));
graph[b].Add((a, 1 / values[i]));
}
return queries.Select(q => {
string s = q[0], t = q[1];
if (!graph.ContainsKey(s) || !graph.ContainsKey(t)) return -1.0;
var seen = new HashSet<string> { s };
var queue = new Queue<(string u, double product)>();
queue.Enqueue((s, 1.0));
while (queue.Count > 0) { // a path's value is the product of its edges
var (u, product) = queue.Dequeue();
if (u == t) return product;
foreach (var (v, x) in graph[u])
if (seen.Add(v)) queue.Enqueue((v, product * x));
}
return -1.0;
}).ToArray();
}
static void Main() {
var queries = new[] { new[] {"x", "w"}, new[] {"w", "y"}, new[] {"y", "x"}, new[] {"x", "q"}, new[] {"z", "z"} };
var answers = CalcEquation(new[] { new[] {"x", "y"}, new[] {"y", "z"}, new[] {"z", "w"} }, new[] {4.0, 0.5, 3.0},
queries);
Console.WriteLine(string.Join(" | ", queries.Select((q, i) =>
$"{q[0]} / {q[1]} = {answers[i].ToString("F5", CultureInfo.InvariantCulture)}")));
}
}
// x / w = 6.00000 | w / y = 0.66667 | y / x = 0.25000 | x / q = -1.00000 | z / z = 1.00000package main
import (
"fmt"
"strings"
)
type edge struct {
v string
x float64
}
func calcEquation(equations [][2]string, values []float64, queries [][2]string) []float64 { // a / b = x
graph := map[string][]edge{} // an edge a -> b of x, and b -> a of 1/x
for i, e := range equations {
graph[e[0]] = append(graph[e[0]], edge{e[1], values[i]})
graph[e[1]] = append(graph[e[1]], edge{e[0], 1 / values[i]})
}
answers := []float64{}
for _, q := range queries {
s, t := q[0], q[1]
found := -1.0
_, okS := graph[s]
_, okT := graph[t]
if okS && okT {
seen := map[string]bool{s: true}
queue := []edge{{s, 1.0}}
for head := 0; head < len(queue); head++ { // a path's value is the product of its edges
u, product := queue[head].v, queue[head].x
if u == t {
found = product
break
}
for _, e := range graph[u] {
if !seen[e.v] {
seen[e.v] = true
queue = append(queue, edge{e.v, product * e.x})
}
}
}
}
answers = append(answers, found)
}
return answers
}
func main() {
queries := [][2]string{{"x", "w"}, {"w", "y"}, {"y", "x"}, {"x", "q"}, {"z", "z"}}
answers := calcEquation([][2]string{{"x", "y"}, {"y", "z"}, {"z", "w"}}, []float64{4.0, 0.5, 3.0}, queries)
parts := []string{}
for i, q := range queries {
parts = append(parts, fmt.Sprintf("%s / %s = %.5f", q[0], q[1], answers[i]))
}
fmt.Println(strings.Join(parts, " | "))
}
// x / w = 6.00000 | w / y = 0.66667 | y / x = 0.25000 | x / q = -1.00000 | z / z = 1.00000x / w multiplies 4, 0.5 and 3: 6. w / y goes back along two edges, 1/3 and 1/0.5, which is 0.66667. q is in no equation, so −1, and z / z is 1.
A*: aim the search
Dijkstra spreads out in rings, whichever way the target lies. A* orders the heap by the distance so far plus a guess of the distance left, here the Manhattan distance, on a grid where every step costs 1. The guess never overestimates, so the first time the target comes off, its distance is still the shortest; but the search heads for the target instead of everywhere:
import heapq
R = C = 40 # a grid of 40 x 40, every step costing 1; from row 5, column 5 to column 35
START, GOAL = (5, 5), (5, 35)
def search(walls, aim): # aim: order by steps so far + the Manhattan distance left (A*)
def h(r, c):
return abs(r - GOAL[0]) + abs(c - GOAL[1]) if aim else 0
g = {START: 0}
heap = [(h(*START), 0, START[0] * C + START[1])] # (f, g, cell): a tie goes to the smaller g, then the cell
done, taken = set(), 0
while heap:
f, steps, cell = heapq.heappop(heap)
if cell in done:
continue
done.add(cell)
taken += 1
r, c = divmod(cell, C)
if (r, c) == GOAL:
return steps, taken
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in walls and steps + 1 < g.get((nr, nc), float("inf")):
g[(nr, nc)] = steps + 1
heapq.heappush(heap, (steps + 1 + h(nr, nc), steps + 1, nr * C + nc))
return -1, taken
for name, walls in (("an open grid", set()), ("a wall in the way", {(r, 20) for r in range(30)})):
(d1, dijkstra), (d2, astar) = search(walls, False), search(walls, True)
print(f"{name}: Dijkstra takes {dijkstra} cells off, A* {astar}; both find {d1} steps" if d1 == d2 else "different")
# an open grid: Dijkstra takes 766 cells off, A* 31; both find 30 steps
# a wall in the way: Dijkstra takes 1521 cells off, A* 996; both find 80 stepsimport java.util.*;
public class Main {
static final int R = 40, C = 40; // a grid of 40 x 40, every step costing 1
static final int[] START = {5, 5}, GOAL = {5, 35};
static int[] search(boolean[][] wall, boolean aim) { // aim: by steps so far + the Manhattan distance left (A*)
int[] g = new int[R * C];
Arrays.fill(g, Integer.MAX_VALUE);
boolean[] done = new boolean[R * C];
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
: a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[2], b[2])); // {f, g, cell}
int start = START[0] * C + START[1];
g[start] = 0;
heap.add(new int[] {aim ? h(START[0], START[1]) : 0, 0, start});
int taken = 0;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!heap.isEmpty()) {
int[] top = heap.poll();
int steps = top[1], cell = top[2];
if (done[cell]) continue;
done[cell] = true;
taken++;
int r = cell / C, c = cell % C;
if (r == GOAL[0] && c == GOAL[1]) return new int[] {steps, taken};
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || wall[nr][nc] || steps + 1 >= g[nr * C + nc]) continue;
g[nr * C + nc] = steps + 1;
heap.add(new int[] {steps + 1 + (aim ? h(nr, nc) : 0), steps + 1, nr * C + nc});
}
}
return new int[] {-1, taken};
}
static int h(int r, int c) {
return Math.abs(r - GOAL[0]) + Math.abs(c - GOAL[1]);
}
public static void main(String[] args) {
boolean[][] open = new boolean[R][C], walled = new boolean[R][C];
for (int r = 0; r < 30; r++) walled[r][20] = true;
String[] names = {"an open grid", "a wall in the way"};
boolean[][][] grids = {open, walled};
for (int i = 0; i < 2; i++) {
int[] dijkstra = search(grids[i], false), astar = search(grids[i], true);
System.out.println(dijkstra[0] == astar[0] ? names[i] + ": Dijkstra takes " + dijkstra[1] + " cells off, A* "
+ astar[1] + "; both find " + dijkstra[0] + " steps" : "different");
}
}
}
// an open grid: Dijkstra takes 766 cells off, A* 31; both find 30 steps
// a wall in the way: Dijkstra takes 1521 cells off, A* 996; both find 80 steps#include <bits/stdc++.h>
using namespace std;
const int R = 40, C = 40; // a grid of 40 x 40, every step costing 1
const int SR = 5, SC = 5, GR = 5, GC = 35; // from row 5, column 5 to row 5, column 35
int h(int r, int c) { return abs(r - GR) + abs(c - GC); }
pair<int, int> search(const vector<vector<char>>& wall, bool aim) { // aim: steps so far + Manhattan distance left
vector<int> g(R * C, INT_MAX);
vector<char> done(R * C, 0);
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> heap; // {f, g, cell}
g[SR * C + SC] = 0;
heap.push({aim ? h(SR, SC) : 0, 0, SR * C + SC});
int taken = 0;
const int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!heap.empty()) {
auto [f, steps, cell] = heap.top();
heap.pop();
if (done[cell]) continue;
done[cell] = 1;
taken++;
int r = cell / C, c = cell % C;
if (r == GR && c == GC) return {steps, taken};
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || wall[nr][nc] || steps + 1 >= g[nr * C + nc]) continue;
g[nr * C + nc] = steps + 1;
heap.push({steps + 1 + (aim ? h(nr, nc) : 0), steps + 1, nr * C + nc});
}
}
return {-1, taken};
}
int main() {
vector<vector<char>> open(R, vector<char>(C, 0)), walled = open;
for (int r = 0; r < 30; r++) walled[r][20] = 1;
vector<pair<string, vector<vector<char>>>> grids = {{"an open grid", open}, {"a wall in the way", walled}};
for (auto& [name, wall] : grids) {
auto [d1, dijkstra] = search(wall, false);
auto [d2, astar] = search(wall, true);
if (d1 != d2) cout << "different\n";
else cout << name << ": Dijkstra takes " << dijkstra << " cells off, A* " << astar << "; both find " << d1 << " steps\n";
}
}
// an open grid: Dijkstra takes 766 cells off, A* 31; both find 30 steps
// a wall in the way: Dijkstra takes 1521 cells off, A* 996; both find 80 stepsclass Heap { // a min-heap of arrays, compared item by item
constructor() { this.a = []; }
get size() { return this.a.length; }
less(i, j) {
const x = this.a[i], y = this.a[j];
for (let k = 0; k < x.length; k++) if (x[k] !== y[k]) return x[k] < y[k];
return false;
}
push(item) {
const a = this.a;
a.push(item);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length) {
a[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(l, m)) m = l;
if (r < a.length && this.less(r, m)) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
const R = 40, C = 40; // a grid of 40 x 40, every step costing 1; row 5: column 5 to column 35
const START = [5, 5], GOAL = [5, 35];
const h = (r, c) => Math.abs(r - GOAL[0]) + Math.abs(c - GOAL[1]);
function search(wall, aim) { // aim: order by steps so far + the Manhattan distance left (A*)
const g = new Array(R * C).fill(Infinity), done = new Array(R * C).fill(false);
const heap = new Heap(); // [f, g, cell]: a tie goes to the smaller g, then the cell
const start = START[0] * C + START[1];
g[start] = 0;
heap.push([aim ? h(START[0], START[1]) : 0, 0, start]);
let taken = 0;
while (heap.size) {
const [, steps, cell] = heap.pop();
if (done[cell]) continue;
done[cell] = true;
taken++;
const r = Math.floor(cell / C), c = cell % C;
if (r === GOAL[0] && c === GOAL[1]) return [steps, taken];
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= R || nc < 0 || nc >= C || wall[nr][nc] || steps + 1 >= g[nr * C + nc]) continue;
g[nr * C + nc] = steps + 1;
heap.push([steps + 1 + (aim ? h(nr, nc) : 0), steps + 1, nr * C + nc]);
}
}
return [-1, taken];
}
const open = Array.from({ length: R }, () => new Array(C).fill(false));
const walled = Array.from({ length: R }, (_, r) => Array.from({ length: C }, (_, c) => c === 20 && r < 30));
for (const [name, wall] of [["an open grid", open], ["a wall in the way", walled]]) {
const [d1, dijkstra] = search(wall, false), [d2, astar] = search(wall, true);
console.log(d1 === d2 ? `${name}: Dijkstra takes ${dijkstra} cells off, A* ${astar}; both find ${d1} steps` : "different");
}
// an open grid: Dijkstra takes 766 cells off, A* 31; both find 30 steps
// a wall in the way: Dijkstra takes 1521 cells off, A* 996; both find 80 stepsclass Heap { // a min-heap of arrays, compared item by item
private a: number[][] = [];
get size(): number { return this.a.length; }
private less(i: number, j: number): boolean {
const x = this.a[i], y = this.a[j];
for (let k = 0; k < x.length; k++) if (x[k] !== y[k]) return x[k] < y[k];
return false;
}
push(item: number[]): void {
const a = this.a;
a.push(item);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop(): number[] {
const a = this.a, top = a[0], last = a.pop()!;
if (a.length) {
a[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(l, m)) m = l;
if (r < a.length && this.less(r, m)) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
const R = 40, C = 40; // a grid of 40 x 40, every step costing 1; row 5: column 5 to column 35
const START = [5, 5], GOAL = [5, 35];
const h = (r: number, c: number): number => Math.abs(r - GOAL[0]) + Math.abs(c - GOAL[1]);
function search(wall: boolean[][], aim: boolean): [number, number] { // aim: steps so far + Manhattan left (A*)
const g: number[] = new Array(R * C).fill(Infinity), done: boolean[] = new Array(R * C).fill(false);
const heap = new Heap(); // [f, g, cell]: a tie goes to the smaller g, then the cell
const start = START[0] * C + START[1];
g[start] = 0;
heap.push([aim ? h(START[0], START[1]) : 0, 0, start]);
let taken = 0;
while (heap.size) {
const [, steps, cell] = heap.pop();
if (done[cell]) continue;
done[cell] = true;
taken++;
const r = Math.floor(cell / C), c = cell % C;
if (r === GOAL[0] && c === GOAL[1]) return [steps, taken];
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= R || nc < 0 || nc >= C || wall[nr][nc] || steps + 1 >= g[nr * C + nc]) continue;
g[nr * C + nc] = steps + 1;
heap.push([steps + 1 + (aim ? h(nr, nc) : 0), steps + 1, nr * C + nc]);
}
}
return [-1, taken];
}
const open: boolean[][] = Array.from({ length: R }, () => new Array<boolean>(C).fill(false));
const walled: boolean[][] = Array.from({ length: R }, (_, r) => Array.from({ length: C }, (_, c) => c === 20 && r < 30));
const grids: [string, boolean[][]][] = [["an open grid", open], ["a wall in the way", walled]];
for (const [name, wall] of grids) {
const [d1, dijkstra] = search(wall, false), [d2, astar] = search(wall, true);
console.log(d1 === d2 ? `${name}: Dijkstra takes ${dijkstra} cells off, A* ${astar}; both find ${d1} steps` : "different");
}
// an open grid: Dijkstra takes 766 cells off, A* 31; both find 30 steps
// a wall in the way: Dijkstra takes 1521 cells off, A* 996; both find 80 stepsusing System;
using System.Collections.Generic;
class Program {
const int R = 40, C = 40; // a grid of 40 x 40, every step costing 1
static readonly int[] Start = {5, 5}, Goal = {5, 35};
static int H(int r, int c) => Math.Abs(r - Goal[0]) + Math.Abs(c - Goal[1]);
static (int, int) Search(bool[,] wall, bool aim) { // aim: by steps so far + the Manhattan distance left (A*)
var g = new int[R * C];
Array.Fill(g, int.MaxValue);
var done = new bool[R * C];
var heap = new PriorityQueue<int, (int, int, int)>(); // a cell, ordered by (f, g, cell)
int start = Start[0] * C + Start[1];
g[start] = 0;
heap.Enqueue(start, (aim ? H(Start[0], Start[1]) : 0, 0, start));
int taken = 0;
int[][] dirs = { new[] {1, 0}, new[] {-1, 0}, new[] {0, 1}, new[] {0, -1} };
while (heap.TryDequeue(out int cell, out var key)) {
int steps = key.Item2;
if (done[cell]) continue;
done[cell] = true;
taken++;
int r = cell / C, c = cell % C;
if (r == Goal[0] && c == Goal[1]) return (steps, taken);
foreach (var d in dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || wall[nr, nc] || steps + 1 >= g[nr * C + nc]) continue;
g[nr * C + nc] = steps + 1;
heap.Enqueue(nr * C + nc, (steps + 1 + (aim ? H(nr, nc) : 0), steps + 1, nr * C + nc));
}
}
return (-1, taken);
}
static void Main() {
var open = new bool[R, C];
var walled = new bool[R, C];
for (int r = 0; r < 30; r++) walled[r, 20] = true;
foreach (var (name, wall) in new[] { ("an open grid", open), ("a wall in the way", walled) }) {
var (d1, dijkstra) = Search(wall, false);
var (d2, astar) = Search(wall, true);
Console.WriteLine(d1 == d2 ? $"{name}: Dijkstra takes {dijkstra} cells off, A* {astar}; both find {d1} steps" : "different");
}
}
}
// an open grid: Dijkstra takes 766 cells off, A* 31; both find 30 steps
// a wall in the way: Dijkstra takes 1521 cells off, A* 996; both find 80 stepspackage main
import (
"container/heap"
"fmt"
"math"
)
type node struct{ f, g, cell int }
type nodeHeap []node // ordered by f, then g, then cell
func (h nodeHeap) Len() int { return len(h) }
func (h nodeHeap) Less(i, j int) bool {
a, b := h[i], h[j]
if a.f != b.f {
return a.f < b.f
}
if a.g != b.g {
return a.g < b.g
}
return a.cell < b.cell
}
func (h nodeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *nodeHeap) Push(x interface{}) { *h = append(*h, x.(node)) }
func (h *nodeHeap) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
const R, C = 40, 40 // a grid of 40 x 40, every step costing 1; row 5: column 5 to column 35
var start, goal = [2]int{5, 5}, [2]int{5, 35}
func manhattan(r, c int) int {
dr, dc := r-goal[0], c-goal[1]
if dr < 0 {
dr = -dr
}
if dc < 0 {
dc = -dc
}
return dr + dc
}
func search(wall [][]bool, aim bool) (int, int) { // aim: order by steps so far + the Manhattan distance left (A*)
h := func(r, c int) int {
if aim {
return manhattan(r, c)
}
return 0
}
g := make([]int, R*C)
for i := range g {
g[i] = math.MaxInt64
}
done := make([]bool, R*C)
s := start[0]*C + start[1]
g[s] = 0
pq := &nodeHeap{{h(start[0], start[1]), 0, s}}
taken := 0
dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for pq.Len() > 0 {
top := heap.Pop(pq).(node)
if done[top.cell] {
continue
}
done[top.cell] = true
taken++
r, c := top.cell/C, top.cell%C
if r == goal[0] && c == goal[1] {
return top.g, taken
}
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= R || nc < 0 || nc >= C || wall[nr][nc] || top.g+1 >= g[nr*C+nc] {
continue
}
g[nr*C+nc] = top.g + 1
heap.Push(pq, node{top.g + 1 + h(nr, nc), top.g + 1, nr*C + nc})
}
}
return -1, taken
}
func main() {
open, walled := make([][]bool, R), make([][]bool, R)
for r := range open {
open[r], walled[r] = make([]bool, C), make([]bool, C)
walled[r][20] = r < 30
}
names := []string{"an open grid", "a wall in the way"}
for i, wall := range [][][]bool{open, walled} {
d1, dijkstra := search(wall, false)
d2, astar := search(wall, true)
if d1 != d2 {
fmt.Println("different")
continue
}
fmt.Printf("%s: Dijkstra takes %d cells off, A* %d; both find %d steps\n", names[i], dijkstra, astar, d1)
}
}
// an open grid: Dijkstra takes 766 cells off, A* 31; both find 30 steps
// a wall in the way: Dijkstra takes 1521 cells off, A* 996; both find 80 stepsOn the open grid A* took 31 cells off, the straight line, where Dijkstra took 766. With a wall in the way the guess is too hopeful beside the wall, so A* spreads around it too: 996 cells against 1,521, and both find the same 80 steps. The better the guess, the less A* searches; a guess of 0 is Dijkstra.
Which one to use
| The graph | Use | Time |
|---|---|---|
| Every step costs the same | BFS | O(V + E) |
| Steps cost 0 or 1 | 0-1 BFS, a deque | O(V + E) |
| No negative weight, one source | Dijkstra, a heap | O((V + E) log V) |
| Negative weights, or at most k edges | Bellman-Ford | O(V × E) |
| A DAG, any weights | Relax in topological order | O(V + E) |
| Every pair, n in the hundreds | Floyd-Warshall | O(n³) |
| One target and a guess of what's left | A* | Less than Dijkstra |
Near misses: BFS and 0-1 BFS are Shortest Paths with BFS; the cheapest way to connect every vertex, rather than to reach one, is a minimum spanning tree, in Union-Find and Minimum Spanning Trees.
Mistakes that look right
Two of these run below in every language. The others are just as common:
- Relaxing in place for k stops: one round strings several flights together.
- k as the inner loop of Floyd-Warshall: a pair is finished before the paths it needs.
- Dijkstra with a negative edge: a vertex settled early is never undercut, as above.
- No stale check: a vertex settled again from an old entry, its edges relaxed again for nothing.
- A plain queue for weighted edges: right, but 1,595,745 cells taken off for 90,000.
- Infinity plus a weight: with the largest integer standing for infinity, adding a weight overflows to a negative number in languages with fixed-size integers; test for infinity first, or pick a smaller infinity.
- The sum where the largest step counts: Path With Minimum Effort's cost is a max, not a total.
def cheapest(n, flights, src, dst, k, from_copy): # Cheapest Flights, each round from a copy or in place
cost = [float("inf")] * n
cost[src] = 0
for _ in range(k + 1):
before = cost[:] if from_copy else cost
for u, v, price in flights:
if before[u] + price < cost[v]:
cost[v] = before[u] + price
return -1 if cost[dst] == float("inf") else cost[dst]
def floyd(n, edges, k_outside): # Floyd-Warshall with k as the outer loop, or the inner one
d = [[0 if i == j else float("inf") for j in range(n)] for i in range(n)]
for u, v, w in edges:
d[u][v] = w
rounds = range(n)
if k_outside:
for k in rounds:
for i in rounds:
for j in rounds:
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
else:
for i in rounds:
for j in rounds:
for k in rounds:
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
return d
flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 3, 400], [1, 3, 300], [0, 2, 200]]
print("k = 0, relaxed in place:", cheapest(4, flights, 0, 3, 0, False), "| from a copy:", cheapest(4, flights, 0, 3, 0, True))
edges = [(0, 1, 1), (1, 3, 1), (3, 2, 1), (0, 2, 10)]
print("0 to 2 with k inside:", floyd(4, edges, False)[0][2], "| with k outside:", floyd(4, edges, True)[0][2])
# k = 0, relaxed in place: 150 | from a copy: 400
# 0 to 2 with k inside: 10 | with k outside: 3import java.util.*;
public class Main {
static final long INF = Long.MAX_VALUE / 4;
static long cheapest(int n, int[][] flights, int src, int dst, int k, boolean fromCopy) { // copy or in place
long[] cost = new long[n];
Arrays.fill(cost, INF);
cost[src] = 0;
for (int round = 0; round <= k; round++) {
long[] before = fromCopy ? cost.clone() : cost;
for (int[] f : flights) if (before[f[0]] + f[2] < cost[f[1]]) cost[f[1]] = before[f[0]] + f[2];
}
return cost[dst] >= INF ? -1 : cost[dst];
}
static long[][] floyd(int n, int[][] edges, boolean kOutside) { // k as the outer loop, or the inner one
long[][] d = new long[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(d[i], INF);
d[i][i] = 0;
}
for (int[] e : edges) d[e[0]][e[1]] = e[2];
if (kOutside) {
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
} else {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++) d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
}
return d;
}
public static void main(String[] args) {
int[][] flights = {{0, 1, 50}, {1, 2, 50}, {2, 3, 50}, {0, 3, 400}, {1, 3, 300}, {0, 2, 200}};
System.out.println("k = 0, relaxed in place: " + cheapest(4, flights, 0, 3, 0, false) + " | from a copy: "
+ cheapest(4, flights, 0, 3, 0, true));
int[][] edges = {{0, 1, 1}, {1, 3, 1}, {3, 2, 1}, {0, 2, 10}};
System.out.println("0 to 2 with k inside: " + floyd(4, edges, false)[0][2] + " | with k outside: "
+ floyd(4, edges, true)[0][2]);
}
}
// k = 0, relaxed in place: 150 | from a copy: 400
// 0 to 2 with k inside: 10 | with k outside: 3#include <bits/stdc++.h>
using namespace std;
const long long INF = LLONG_MAX / 4;
long long cheapest(int n, const vector<array<int, 3>>& flights, int src, int dst, int k, bool fromCopy) {
vector<long long> cost(n, INF); // Cheapest Flights, each round from a copy or in place
cost[src] = 0;
for (int round = 0; round <= k; round++) {
vector<long long> copy = cost;
vector<long long>& before = fromCopy ? copy : cost;
for (auto& f : flights) if (before[f[0]] + f[2] < cost[f[1]]) cost[f[1]] = before[f[0]] + f[2];
}
return cost[dst] >= INF ? -1 : cost[dst];
}
vector<vector<long long>> floyd(int n, const vector<array<int, 3>>& edges, bool kOutside) { // k outer, or inner
vector<vector<long long>> d(n, vector<long long>(n, INF));
for (int i = 0; i < n; i++) d[i][i] = 0;
for (auto& e : edges) d[e[0]][e[1]] = e[2];
if (kOutside) {
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
} else {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
return d;
}
int main() {
vector<array<int, 3>> flights = {{0, 1, 50}, {1, 2, 50}, {2, 3, 50}, {0, 3, 400}, {1, 3, 300}, {0, 2, 200}};
cout << "k = 0, relaxed in place: " << cheapest(4, flights, 0, 3, 0, false) << " | from a copy: "
<< cheapest(4, flights, 0, 3, 0, true) << "\n";
vector<array<int, 3>> edges = {{0, 1, 1}, {1, 3, 1}, {3, 2, 1}, {0, 2, 10}};
cout << "0 to 2 with k inside: " << floyd(4, edges, false)[0][2] << " | with k outside: " << floyd(4, edges, true)[0][2]
<< "\n";
}
// k = 0, relaxed in place: 150 | from a copy: 400
// 0 to 2 with k inside: 10 | with k outside: 3function cheapest(n, flights, src, dst, k, fromCopy) { // Cheapest Flights, each round from a copy or in place
const cost = new Array(n).fill(Infinity);
cost[src] = 0;
for (let round = 0; round <= k; round++) {
const before = fromCopy ? [...cost] : cost;
for (const [u, v, price] of flights) if (before[u] + price < cost[v]) cost[v] = before[u] + price;
}
return cost[dst] === Infinity ? -1 : cost[dst];
}
function floyd(n, edges, kOutside) { // Floyd-Warshall with k as the outer loop, or the inner one
const d = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
for (const [u, v, w] of edges) d[u][v] = w;
const relax = (i, j, k) => { d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]); };
for (let a = 0; a < n; a++)
for (let b = 0; b < n; b++)
for (let c = 0; c < n; c++) {
if (kOutside) relax(b, c, a); // k = a, the outermost
else relax(a, b, c); // k = c, the innermost
}
return d;
}
const flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 3, 400], [1, 3, 300], [0, 2, 200]];
console.log(`k = 0, relaxed in place: ${cheapest(4, flights, 0, 3, 0, false)} | from a copy: ${cheapest(4, flights, 0, 3, 0, true)}`);
const edges = [[0, 1, 1], [1, 3, 1], [3, 2, 1], [0, 2, 10]];
console.log(`0 to 2 with k inside: ${floyd(4, edges, false)[0][2]} | with k outside: ${floyd(4, edges, true)[0][2]}`);
// k = 0, relaxed in place: 150 | from a copy: 400
// 0 to 2 with k inside: 10 | with k outside: 3function cheapest(n: number, flights: number[][], src: number, dst: number, k: number, fromCopy: boolean): number {
const cost: number[] = new Array(n).fill(Infinity); // Cheapest Flights, each round from a copy or in place
cost[src] = 0;
for (let round = 0; round <= k; round++) {
const before = fromCopy ? [...cost] : cost;
for (const [u, v, price] of flights) if (before[u] + price < cost[v]) cost[v] = before[u] + price;
}
return cost[dst] === Infinity ? -1 : cost[dst];
}
function floyd(n: number, edges: number[][], kOutside: boolean): number[][] { // k as the outer loop, or inner
const d: number[][] = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
for (const [u, v, w] of edges) d[u][v] = w;
const relax = (i: number, j: number, k: number): void => { d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]); };
for (let a = 0; a < n; a++)
for (let b = 0; b < n; b++)
for (let c = 0; c < n; c++) {
if (kOutside) relax(b, c, a); // k = a, the outermost
else relax(a, b, c); // k = c, the innermost
}
return d;
}
const flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 3, 400], [1, 3, 300], [0, 2, 200]];
console.log(`k = 0, relaxed in place: ${cheapest(4, flights, 0, 3, 0, false)} | from a copy: ${cheapest(4, flights, 0, 3, 0, true)}`);
const edges = [[0, 1, 1], [1, 3, 1], [3, 2, 1], [0, 2, 10]];
console.log(`0 to 2 with k inside: ${floyd(4, edges, false)[0][2]} | with k outside: ${floyd(4, edges, true)[0][2]}`);
// k = 0, relaxed in place: 150 | from a copy: 400
// 0 to 2 with k inside: 10 | with k outside: 3using System;
class Program {
const long INF = long.MaxValue / 4;
static long Cheapest(int n, int[][] flights, int src, int dst, int k, bool fromCopy) { // a copy, or in place
var cost = new long[n];
Array.Fill(cost, INF);
cost[src] = 0;
for (int round = 0; round <= k; round++) {
var before = fromCopy ? (long[]) cost.Clone() : cost;
foreach (var f in flights) if (before[f[0]] + f[2] < cost[f[1]]) cost[f[1]] = before[f[0]] + f[2];
}
return cost[dst] >= INF ? -1 : cost[dst];
}
static long[,] Floyd(int n, int[][] edges, bool kOutside) { // k as the outer loop, or the inner one
var d = new long[n, n];
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i, j] = i == j ? 0 : INF;
foreach (var e in edges) d[e[0], e[1]] = e[2];
if (kOutside) {
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) d[i, j] = Math.Min(d[i, j], d[i, k] + d[k, j]);
} else {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++) d[i, j] = Math.Min(d[i, j], d[i, k] + d[k, j]);
}
return d;
}
static void Main() {
int[][] flights = { new[] {0, 1, 50}, new[] {1, 2, 50}, new[] {2, 3, 50}, new[] {0, 3, 400}, new[] {1, 3, 300},
new[] {0, 2, 200} };
Console.WriteLine($"k = 0, relaxed in place: {Cheapest(4, flights, 0, 3, 0, false)} | from a copy: {Cheapest(4, flights, 0, 3, 0, true)}");
int[][] edges = { new[] {0, 1, 1}, new[] {1, 3, 1}, new[] {3, 2, 1}, new[] {0, 2, 10} };
Console.WriteLine($"0 to 2 with k inside: {Floyd(4, edges, false)[0, 2]} | with k outside: {Floyd(4, edges, true)[0, 2]}");
}
}
// k = 0, relaxed in place: 150 | from a copy: 400
// 0 to 2 with k inside: 10 | with k outside: 3package main
import (
"fmt"
"math"
)
const INF = math.MaxInt64 / 4
func cheapest(n int, flights [][3]int, src, dst, k int, fromCopy bool) int { // each round from a copy, or in place
cost := make([]int, n)
for i := range cost {
cost[i] = INF
}
cost[src] = 0
for round := 0; round <= k; round++ {
before := cost
if fromCopy {
before = append([]int{}, cost...)
}
for _, f := range flights {
if before[f[0]]+f[2] < cost[f[1]] {
cost[f[1]] = before[f[0]] + f[2]
}
}
}
if cost[dst] >= INF {
return -1
}
return cost[dst]
}
func floyd(n int, edges [][3]int, kOutside bool) [][]int { // Floyd-Warshall with k as the outer loop, or the inner one
d := make([][]int, n)
for i := range d {
d[i] = make([]int, n)
for j := range d[i] {
if i != j {
d[i][j] = INF
}
}
}
for _, e := range edges {
d[e[0]][e[1]] = e[2]
}
relax := func(i, j, k int) {
if d[i][k]+d[k][j] < d[i][j] {
d[i][j] = d[i][k] + d[k][j]
}
}
for a := 0; a < n; a++ {
for b := 0; b < n; b++ {
for c := 0; c < n; c++ {
if kOutside {
relax(b, c, a) // k = a, the outermost
} else {
relax(a, b, c) // k = c, the innermost
}
}
}
}
return d
}
func main() {
flights := [][3]int{{0, 1, 50}, {1, 2, 50}, {2, 3, 50}, {0, 3, 400}, {1, 3, 300}, {0, 2, 200}}
fmt.Printf("k = 0, relaxed in place: %d | from a copy: %d\n", cheapest(4, flights, 0, 3, 0, false), cheapest(4, flights, 0, 3, 0, true))
edges := [][3]int{{0, 1, 1}, {1, 3, 1}, {3, 2, 1}, {0, 2, 10}}
fmt.Printf("0 to 2 with k inside: %d | with k outside: %d\n", floyd(4, edges, false)[0][2], floyd(4, edges, true)[0][2])
}
// k = 0, relaxed in place: 150 | from a copy: 400
// 0 to 2 with k inside: 10 | with k outside: 3Relaxed in place, the round for k = 0 followed 0 → 1, then 1 → 2, then 2 → 3 in one pass, each flight reading a cost the same round had just written: 150 for three flights, where the direct flight's 400 is the only trip with no stop. With k innermost, d[0][2] was finished at 10 before d[0][3] and d[1][2] were known, so the way 0 → 1 → 3 → 2, for 3, was never seen.
Check yourself
Quiz
1 / 6Multiple choice
Dijkstra runs from 0 on the edges [0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1] and [2, 3, 5]. In what order are the vertices settled?
Multiple choice
A vertex comes off Dijkstra's heap with a distance larger than the one already known for it. What should happen?
Multiple choice
Why can't Dijkstra handle a negative edge?
Multiple choice
Flights [0, 1, 10], [1, 2, 10], [0, 2, 50], [2, 3, 10] and [1, 3, 40]. What's the cheapest trip from 0 to 3 with at most 1 stop?
Multiple choice
In Floyd-Warshall, why must k be the outermost loop?
Multiple choice
A* guesses the distance left with the Manhattan distance, on a grid where every step costs 1. Why is the first path it finds to the target a shortest one?
Practice
The problems in this group, each mapped to the idea it trains:
- Network Delay Time: Dijkstra from one node; the answer is the largest distance.
- Dijkstra's Algorithm: every distance from one source, with a heap.
- Dijkstra: Queue vs Priority Queue: why the nearest first.
- Path With Minimum Effort: max where the sum was.
- Number of Ways to Arrive at Destination: a count beside each distance.
- Cheapest Flights Within K Stops: k + 1 rounds from a copy.
- Bellman-Ford Algorithm: n − 1 rounds, and one more for a negative cycle.
- Shortest Path in DAG: one pass in topological order.
- Floyd-Warshall Algorithm: every pair, k outermost.
- Find the City With the Smallest Number of Neighbors at a Threshold Distance: read the matrix.
- Evaluate Division: ratios as weights, multiplied along a path.