Bellman-Ford Algoritması

1type Edge = { from: string; to: string; weight: number };
2
3function bellmanFord(vertices: string[], edges: Edge[], source: string) {
4  const distance = new Map(vertices.map((vertex) => [vertex, Infinity]));
5  distance.set(source, 0);
6  for (let pass = 1; pass < vertices.length; pass += 1) {
7    for (const edge of edges) {
8      const candidate = distance.get(edge.from)! + edge.weight;
9      if (candidate < distance.get(edge.to)!) {
10        distance.set(edge.to, candidate);
11      }
12    }
13  }
14  const hasNegativeCycle = edges.some((edge) => distance.get(edge.from)! + edge.weight < distance.get(edge.to)!);
15  return { distance, hasNegativeCycle };
16}