Беллман-Форд

1function bellmanFord(edges: Edge[], start: string): Map<string, number> {
2  const dist = new Map<string, number>()
3  for (const v of vertices(edges)) dist.set(v, Infinity)
4  dist.set(start, 0)
5 
6  // V − 1 проход по ВСЕМ рёбрам
7  for (let pass = 1; pass < vertices(edges).length; pass++) {
8    for (const e of edges) {
9      const candidate = (dist.get(e.from) ?? Infinity) + e.weight
10      if (candidate < (dist.get(e.to) ?? Infinity)) {
11        dist.set(e.to, candidate)
12      }
13    }
14  }
15 
16  // ещё один проход: если что-то улучшается — отрицательный цикл
17  for (const e of edges) {
18    if ((dist.get(e.from) ?? Infinity) + e.weight < (dist.get(e.to) ?? Infinity)) {
19      throw new Error('отрицательный цикл')
20    }
21  }
22 
23  return dist
24}