Bellman-Ford یکی از مهم‌ترین الگوریتم‌های Shortest Path است؛ مخصوصاً وقتی Graph دارای Edge با وزن منفی باشد.

برخلاف Dijkstra، Bellman-Ford می‌تواند با:

Code

negative edge weight

کار کند.

و حتی یک قابلیت مهم‌تر دارد:

اگر از Source بتوان به یک Negative Cycle رسید، Bellman-Ford می‌تواند آن را تشخیص دهد.

این ویژگی باعث می‌شود Bellman-Ford فقط یک الگوریتم Shortest Path نباشد؛ بلکه ابزاری برای اعتبارسنجی Graphهای وزن‌دار نیز باشد.

در این مقاله Bellman-Ford را از پایه بررسی می‌کنیم: مفهوم Relaxation، دلیل اجرای V-1 مرحله، تشخیص Negative Cycle، بازسازی Path، Early Stop، تفاوت با Dijkstra، کاربرد در Routing و مدل‌های Credit/Penalty و پیاده‌سازی JavaScript و TypeScript.

Bellman-Ford دقیقاً چه مسئله‌ای را حل می‌کند؟

فرض کنید یک Graph وزن‌دار داریم و می‌خواهیم Shortest Path را از یک Source به همه‌ی Vertexها پیدا کنیم.

مثلاً:

Code

A --4--> B
A --5--> C
B --(-2)--> C

اگر از A شروع کنیم:

مسیر مستقیم:

Code

A → C
cost = 5

اما مسیر:

Code

A → B → C

هزینه:

Code

4 + (-2) = 2

دارد.

پس Shortest Path واقعی:

Code

A → B → C

است.

وجود Edge منفی باعث می‌شود الگوریتم‌هایی مثل Dijkstra در حالت عمومی قابل اعتماد نباشند.

Weight منفی یعنی چه؟

وزن منفی الزاماً چیز غیرواقعی نیست.

می‌تواند مدل‌کننده‌ی:

تخفیف
Credit
سود
کاهش هزینه
Bonus
Offset
Penalty معکوس

باشد.

مثلاً:

Code

Transaction A → B = +10
Transaction B → C = -4

ممکن است یک Edge منفی کاملاً معنی‌دار باشد.

ایده اصلی Bellman-Ford

ایده اصلی بسیار ساده است:

تمام Edgeها را بارها Relax کن تا دیگر هیچ Distanceای بهتر نشود.

این الگوریتم برخلاف Dijkstra سعی نمی‌کند یک Vertex را زود Final کند.

بلکه اجازه می‌دهد اطلاعات Shortest Path در چند Pass روی Graph پخش شود.

Relaxation چیست؟

Relaxation قلب Bellman-Ford است.

برای Edge:

Code

u → v
weight = w

اگر:

Code

dist[u] + w < dist[v]

باشد، یعنی مسیر:

Code

source → ... → u → v

از بهترین مسیر فعلی به v کوتاه‌تر است.

پس:

Code

dist[v] = dist[u] + w

مثال Relaxation

فرض کنید:

Code

dist[A] = 0
dist[B] = Infinity

و Edge:

Code

A → B weight 5

داریم.

چون:

Code

0 + 5 < Infinity

پس:

Code

dist[B] = 5

حالا اگر بعداً مسیر بهتری پیدا شود:

Code

A → C = 2
C → B = 1

آنگاه:

Code

dist[B] = 3

می‌شود.

مقداردهی اولیه

در Single-Source Shortest Path:

Code

dist[source] = 0

و بقیه:

Code

Infinity

مثلاً:

Code

A = 0
B = ∞
C = ∞
D = ∞

چرا Infinity؟

چون هنوز هیچ مسیر شناخته‌شده‌ای به آن Node نداریم.

وقتی اولین مسیر پیدا شود، عدد واقعی از Infinity کوچک‌تر خواهد بود.

الگوریتم مرحله‌به‌مرحله

Bellman-Ford:

Distance مبدأ را صفر کن.
Distance بقیه را Infinity کن.
تمام Edgeها را Relax کن.
این کار را V - 1 بار تکرار کن.
یک Pass اضافه روی Edgeها انجام بده.
اگر هنوز Relaxation ممکن بود، Negative Cycle قابل‌دسترسی از Source وجود دارد.

چرا دقیقاً V-1 بار؟

این یکی از مهم‌ترین سؤال‌های مفهومی است.

در Graph با V رأس، یک Shortest Path ساده نمی‌تواند بیش از:

Code

V - 1

Edge داشته باشد.

چرا؟

اگر Path بیش از V-1 Edge داشته باشد، حتماً یک Vertex تکرار شده و Cycle داریم.

اگر Cycle وزن غیرمنفی داشته باشد، حذف آن Path را بدتر نمی‌کند.

اگر Cycle وزن منفی داشته باشد، اصلاً Shortest Path محدود و مشخص نداریم چون می‌توانیم Cycle را بارها تکرار کنیم.

پس برای Graph بدون Negative Cycle مؤثر:

Code

V - 1 relaxation rounds

کافی است.

نگاه دیگری به V-1 Pass

بعد از Pass اول، Shortest Pathهایی که حداکثر یک Edge دارند می‌توانند درست شوند.

بعد از Pass دوم:

Code

حداکثر 2 Edge

بعد از Pass سوم:

Code

حداکثر 3 Edge

و ...

بعد از:

Code

V - 1

Pass تمام Shortest Pathهای ساده پوشش داده شده‌اند.

پیاده‌سازی پایه JavaScript

JavaScript

function bellmanFord(vertices, edges, source) {
  const dist = Object.fromEntries(
    vertices.map(v => [v, Infinity])
  );

  dist[source] = 0;

  for (let i = 0; i < vertices.length - 1; i++) {
    for (const [u, v, w] of edges) {
      if (
        dist[u] !== Infinity &&
        dist[u] + w < dist[v]
      ) {
        dist[v] = dist[u] + w;
      }
    }
  }

  for (const [u, v, w] of edges) {
    if (
      dist[u] !== Infinity &&
      dist[u] + w < dist[v]
    ) {
      throw new Error(
        "Negative cycle reachable from source"
      );
    }
  }

  return dist;
}

چرا شرط dist[u] !== Infinity لازم است؟

اگر u از Source قابل دسترسی نباشد:

Code

dist[u] = Infinity

نباید Edgeهای خروجی آن را Relax کنیم.

در JavaScript:

Code

Infinity + (-5) = Infinity

است، ولی شرط صریح هم Intent را واضح می‌کند و هم منطق الگوریتم را درست نگه می‌دارد.

مثال کامل

Vertexها:

Code

A, B, C, D

Edgeها:

Code

A → B = 4
A → C = 5
B → C = -2
C → D = 3

ابتدا:

Code

A = 0
B = ∞
C = ∞
D = ∞

Pass اول

Edge:

Code

A → B = 4

پس:

Code

B = 4

Edge:

Code

A → C = 5

پس:

Code

C = 5

Edge:

Code

B → C = -2

داریم:

Code

4 + (-2) = 2

پس:

Code

C = 2

Edge:

Code

C → D = 3

پس:

Code

D = 5

نتیجه:

Code

A = 0
B = 4
C = 2
D = 5

آیا همیشه باید V-1 Pass کامل اجرا کنیم؟

نه.

اگر در یک Pass هیچ Distanceای Update نشود، الگوریتم Converge شده است.

می‌توانیم زود متوقف شویم.

Early Stop Optimization

JavaScript

function bellmanFordOptimized(
  vertices,
  edges,
  source
) {
  const dist = Object.fromEntries(
    vertices.map(v => [v, Infinity])
  );

  dist[source] = 0;

  for (let i = 0; i < vertices.length - 1; i++) {
    let updated = false;

    for (const [u, v, w] of edges) {
      if (
        dist[u] !== Infinity &&
        dist[u] + w < dist[v]
      ) {
        dist[v] = dist[u] + w;
        updated = true;
      }
    }

    if (!updated) {
      break;
    }
  }

  return dist;
}

در Worst Case همچنان:

Code

O(VE)

است، اما در بعضی Graphها زودتر تمام می‌شود.

Negative Cycle چیست؟

Cycleای است که مجموع Weightهایش منفی باشد.

مثلاً:

Code

A → B = 2
B → C = -5
C → A = 1

مجموع:

Code

2 - 5 + 1 = -2

پس Cycle وزن:

Code

-2

دارد.

چرا Negative Cycle مشکل ایجاد می‌کند؟

فرض کنید یک بار Cycle را طی کنیم:

Code

cost = -2

دو بار:

Code

cost = -4

سه بار:

Code

cost = -6

و همین‌طور:

Code

-∞

پس Shortest Path معنی مشخصی ندارد.

می‌توانیم هر بار با یک دور دیگر هزینه را کمتر کنیم.

تشخیص Negative Cycle

بعد از V-1 Pass، اگر Graph Negative Cycle قابل‌دسترسی نداشته باشد، هیچ Relaxation دیگری نباید ممکن باشد.

پس یک Pass اضافه می‌زنیم.

اگر هنوز:

Code

dist[u] + w < dist[v]

باشد:

Code

Negative Cycle exists

نکته بسیار مهم: Cycle باید از Source قابل دسترس باشد

فرض کنید Graph دو Component دارد.

Component اول Source در آن است.

Component دوم Negative Cycle دارد اما Source هیچ راهی به آن ندارد.

در Single-Source Bellman-Ford معمولاً آن Cycle روی Distanceهای Source تأثیری ندارد.

به همین دلیل شرط:

JavaScript

dist[u] !== Infinity

در Cycle Detection مهم است.

تشخیص وجود Negative Cycle در کل Graph

اگر بخواهیم بفهمیم هر جای Graph Negative Cycle وجود دارد، نه فقط Reachable از یک Source، می‌توانیم یک Super Source مجازی بسازیم.

به همه Vertexها Edge صفر بدهیم:

Code

S → v
weight = 0

برای همه v.

حالا تمام Graph از S قابل دسترسی است.

Super Source

مثلاً:

Code

S → A = 0
S → B = 0
S → C = 0
S → D = 0

بعد Bellman-Ford را از S اجرا می‌کنیم.

اگر Cycle منفی هر جایی وجود داشته باشد، قابل تشخیص می‌شود.

بازسازی Shortest Path

فقط Distance همیشه کافی نیست.

گاهی می‌خواهیم خود مسیر را هم بدانیم.

برای این کار هنگام Relaxation:

Code

parent[v] = u

ذخیره می‌کنیم.

Bellman-Ford با Parent

JavaScript

function bellmanFordWithPath(
  vertices,
  edges,
  source
) {
  const dist = Object.fromEntries(
    vertices.map(v => [v, Infinity])
  );

  const parent = Object.fromEntries(
    vertices.map(v => [v, null])
  );

  dist[source] = 0;

  for (let i = 0; i < vertices.length - 1; i++) {
    let updated = false;

    for (const [u, v, w] of edges) {
      if (
        dist[u] !== Infinity &&
        dist[u] + w < dist[v]
      ) {
        dist[v] = dist[u] + w;
        parent[v] = u;
        updated = true;
      }
    }

    if (!updated) {
      break;
    }
  }

  return {
    dist,
    parent
  };
}

بازسازی مسیر

JavaScript

function buildPath(parent, source, target) {
  const path = [];

  let current = target;

  while (current !== null) {
    path.push(current);

    if (current === source) {
      return path.reverse();
    }

    current = parent[current];
  }

  return null;
}

اگر Target reachable نباشد:

Code

null

برمی‌گردد.

پیدا کردن خود Negative Cycle

گاهی فقط دانستن:

Code

negative cycle exists

کافی نیست.

مثلاً در Debugging یا Arbitrage Analysis می‌خواهیم Cycle را ببینیم.

یک تکنیک معروف:

در Pass اضافه، آخرین Vertex Update‌شده را ذخیره کن.
از Parent آن Vertex، V بار عقب برو.
حالا حتماً داخل Cycle قرار گرفته‌ای.
Parentها را ادامه بده تا دوباره به همان Vertex برگردی.

ایده بازسازی Negative Cycle

اگر Vertex:

Code

در Pass شماره V Update شود، می‌دانیم تحت تأثیر Negative Cycle قرار گرفته است.

با:

Code

x = parent[x]

به تعداد V بار، Prefix خارج Cycle را حذف می‌کنیم.

بعد Cycle را بازسازی می‌کنیم.

Bellman-Ford vs Dijkstra

این مقایسه بسیار مهم است.

ویژگی	Bellman-Ford	Dijkstra
Negative Edge	بله	خیر، در حالت استاندارد
Negative Cycle Detection	بله	خیر
Complexity	O(VE)	معمولاً O((V+E) log V)
سرعت	کندتر	سریع‌تر
Relaxation	همه Edgeها چندبار	Greedy + Priority Queue
کاربرد اصلی	وزن منفی / cycle detection	وزن غیرمنفی

چرا Dijkstra با وزن منفی مشکل دارد؟

Dijkstra فرض می‌کند وقتی نزدیک‌ترین Vertex را Final کردیم، بعداً Path بهتری پیدا نمی‌شود.

Negative Edge می‌تواند این فرض را بشکند.

مثلاً ممکن است Vertexای زود Final شود ولی بعداً از یک مسیر با Edge منفی Distance بهتری به آن برسد.

Bellman-Ford چنین Finalization زودهنگامی ندارد.

BFS vs Bellman-Ford

اگر Graph بدون وزن باشد:

Code

BFS

بهتر است.

اگر تمام Weightها برابر باشند:

Code

BFS

معمولاً کافی است.

اگر Weightها متفاوت و ممکن است منفی باشند:

Code

Bellman-Ford

مطرح می‌شود.

DAG Shortest Path vs Bellman-Ford

اگر Graph یک DAG باشد، حتی با Weight منفی می‌توان:

Topological Sort گرفت.
Edgeها را در Topological Order Relax کرد.

Complexity:

Code

O(V + E)

که بسیار بهتر از:

Code

O(VE)

است.

پس اگر Graph DAG است، Bellman-Ford لزوماً بهترین گزینه نیست.

Floyd-Warshall vs Bellman-Ford

Bellman-Ford

Single Source:

Code

source → all vertices

Floyd-Warshall

All Pairs:

Code

every vertex → every vertex

Complexity Floyd-Warshall:

Code

O(V³)

پس سؤال مهم این است:

Code

Single Source?
یا
All Pairs?

Johnson's Algorithm

برای All-Pairs Shortest Path در Sparse Graph با Weight منفی ولی بدون Negative Cycle، الگوریتم Johnson مهم است.

Johnson از Bellman-Ford برای Reweight کردن Edgeها استفاده می‌کند و سپس Dijkstra را از هر Vertex اجرا می‌کند.

این نشان می‌دهد Bellman-Ford پایه‌ی الگوریتم‌های پیشرفته‌تر نیز هست.

کاربرد: Distance Vector Routing

Bellman-Ford از نظر مفهومی پایه‌ی الگوریتم‌های Distance Vector Routing است.

هر Router اطلاعات Distance خود را از Neighborها دریافت می‌کند و می‌پرسد:

Code

اگر از Neighbor X بروم،
آیا Route به Destination ارزان‌تر می‌شود؟

این دقیقاً شبیه Relaxation است.

Routing Table

فرم مفهومی:

Code

distance(destination)
=
min over neighbors(
  cost(to neighbor)
  +
  neighbor distance(destination)
)

این همان Dynamic Programming / Bellman equation است.

مشکل Count-to-Infinity

Distance Vector Routing مشکلاتی مثل:

Code

count-to-infinity

دارد.

وقتی Route خراب می‌شود، Routerها ممکن است اطلاعات اشتباه را بین خود پخش کنند و Metric به‌تدریج افزایش پیدا کند.

راهکارهایی مثل:

Split Horizon
Poison Reverse
Hold-down

در Protocolهای Routing مطرح می‌شوند.

پس Bellman-Ford در دنیای Networking فقط یک الگوریتم تئوری نیست.

مدل سود و زیان

فرض کنید Edge Weight نشان‌دهنده Cost باشد.

Negative Weight می‌تواند Discount یا Credit باشد.

مثلاً:

Code

Supplier A → B = +10
B → C = -4

Bellman-Ford می‌تواند Minimum Net Cost را پیدا کند.

Arbitrage و Negative Cycle

در مسائل Currency Arbitrage می‌توان Rateها را با Transformation لگاریتمی به Weight تبدیل کرد.

اگر Cycle مناسب با وزن منفی پیدا شود، می‌تواند نشان‌دهنده فرصت Arbitrage در مدل ریاضی باشد.

البته در بازار واقعی:

fee
spread
liquidity
slippage
timing

هم مهم‌اند.

Credit/Penalty Graph

در بعضی سیستم‌ها Edgeها می‌توانند:

penalty مثبت
credit منفی

داشته باشند.

Bellman-Ford برای چنین Cost Modelهایی طبیعی است.

Constraint Systems

بعضی Difference Constraintها به فرم:

Code

x_v <= x_u + w

هستند.

این Relation دقیقاً شبیه Relaxation Bellman-Ford است.

Negative Cycle می‌تواند نشانه‌ی ناسازگار بودن Constraintها باشد.

Difference Constraints

اگر Constraintها را به Edge تبدیل کنیم:

Code

u → v weight w

Bellman-Ford می‌تواند feasibility سیستم را بررسی کند.

این یکی از کاربردهای نظری و عملی مهم الگوریتم است.

Edge List چرا مناسب Bellman-Ford است؟

Bellman-Ford در هر Pass باید:

Code

all edges

را بررسی کند.

پس Representation طبیعی:

JavaScript

[
  [u, v, w],
  [u, v, w],
  ...
]

است.

Adjacency List هم ممکن است، ولی Edge List ساده‌تر است.

Directed و Undirected Graph

Bellman-Ford برای Directed Graph طبیعی است.

برای Undirected Graph، هر Edge:

Code

u -- v weight w

را می‌توان به دو Directed Edge تبدیل کرد:

Code

u → v weight w
v → u weight w

اما یک نکته مهم وجود دارد.

Weight منفی در Undirected Graph

اگر یک Undirected Edge وزن منفی داشته باشد:

Code

u -- v = -5

معادل دو Edge:

Code

u → v = -5
v → u = -5

است.

پس Cycle:

Code

u → v → u

وزن:

Code

-10

دارد.

بنابراین یک Undirected Negative Edge عملاً Negative Cycle ایجاد می‌کند.

این نکته در مدل‌سازی بسیار مهم است.

Unreachable Vertices

اگر Vertex از Source قابل دسترسی نباشد:

Code

dist[v] = Infinity

باقی می‌ماند.

این Error نیست؛ یعنی Path وجود ندارد.

Empty Graph

اگر Graph Vertex نداشته باشد، باید Source هم وجود نداشته باشد یا Validation انجام شود.

Source نامعتبر

در Production بهتر است بررسی کنیم:

Code

source ∈ vertices

اگر Source در Vertexها نیست، Error واضح برگردانیم.

Duplicate Edges

وجود چند Edge از u به v مشکلی ندارد.

Bellman-Ford همه را Relax می‌کند و بهترین گزینه مؤثر خواهد شد.

Self-loop

Self-loop:

Code

u → u

اگر Weight آن منفی باشد:

Code

negative self-cycle

است.

مثلاً:

Code

u → u = -1

یک Negative Cycle واضح است.

Overflow و Infinity

در زبان‌هایی با Integer محدود باید مراقب Overflow باشیم.

در JavaScript Number از Floating Point استفاده می‌کند، اما باز هم:

Infinity
very large values
precision limits

باید در مدل‌های بزرگ در نظر گرفته شوند.

نسخه کامل‌تر با Result Object

در Production بهتر است به جای throw کردن، Result ساختاری برگردانیم.

JavaScript

function bellmanFordSafe(
  vertices,
  edges,
  source
) {
  const dist = new Map();
  const parent = new Map();

  for (const v of vertices) {
    dist.set(v, Infinity);
    parent.set(v, null);
  }

  if (!dist.has(source)) {
    return {
      ok: false,
      reason: "INVALID_SOURCE"
    };
  }

  dist.set(source, 0);

  for (let i = 0; i < vertices.length - 1; i++) {
    let updated = false;

    for (const [u, v, w] of edges) {
      const du = dist.get(u);
      const dv = dist.get(v);

      if (
        du !== Infinity &&
        du + w < dv
      ) {
        dist.set(v, du + w);
        parent.set(v, u);
        updated = true;
      }
    }

    if (!updated) {
      break;
    }
  }

  for (const [u, v, w] of edges) {
    const du = dist.get(u);
    const dv = dist.get(v);

    if (
      du !== Infinity &&
      du + w < dv
    ) {
      return {
        ok: false,
        reason: "NEGATIVE_CYCLE",
        dist,
        parent
      };
    }
  }

  return {
    ok: true,
    dist,
    parent
  };
}

TypeScript Version

TypeScript

type Vertex = string;

type Edge = [
  from: Vertex,
  to: Vertex,
  weight: number
];

type BellmanFordResult =
  | {
      ok: true;
      dist: Map<Vertex, number>;
      parent: Map<Vertex, Vertex | null>;
    }
  | {
      ok: false;
      reason: "INVALID_SOURCE" | "NEGATIVE_CYCLE";
      dist?: Map<Vertex, number>;
      parent?: Map<Vertex, Vertex | null>;
    };

function bellmanFord(
  vertices: Vertex[],
  edges: Edge[],
  source: Vertex
): BellmanFordResult {
  const dist = new Map<Vertex, number>();
  const parent =
    new Map<Vertex, Vertex | null>();

  for (const v of vertices) {
    dist.set(v, Infinity);
    parent.set(v, null);
  }

  if (!dist.has(source)) {
    return {
      ok: false,
      reason: "INVALID_SOURCE"
    };
  }

  dist.set(source, 0);

  for (
    let i = 0;
    i < vertices.length - 1;
    i++
  ) {
    let updated = false;

    for (const [u, v, w] of edges) {
      const du = dist.get(u)!;
      const dv = dist.get(v)!;

      if (
        du !== Infinity &&
        du + w < dv
      ) {
        dist.set(v, du + w);
        parent.set(v, u);
        updated = true;
      }
    }

    if (!updated) {
      break;
    }
  }

  for (const [u, v, w] of edges) {
    const du = dist.get(u)!;
    const dv = dist.get(v)!;

    if (
      du !== Infinity &&
      du + w < dv
    ) {
      return {
        ok: false,
        reason: "NEGATIVE_CYCLE",
        dist,
        parent
      };
    }
  }

  return {
    ok: true,
    dist,
    parent
  };
}

پیچیدگی زمانی

Bellman-Ford:

Code

V - 1

Pass دارد.

در هر Pass:

Code

Edge بررسی می‌شود.

پس:

Code

Time = O(VE)

پیچیدگی فضایی

برای:

dist
parent

تقریباً:

Code

O(V)

فضای کمکی نیاز داریم.

خود Edge List:

Code

O(E)

فضا دارد.

چه زمانی Bellman-Ford استفاده کنیم؟

وقتی:

Negative Edge داریم.
Negative Cycle Detection لازم است.
Single-Source Shortest Path می‌خواهیم.
Difference Constraints داریم.
Distance Vector logic داریم.
Cost Model شامل Credit/Penalty است.
Dijkstra به دلیل Weight منفی قابل استفاده نیست.

چه زمانی Bellman-Ford بهترین انتخاب نیست؟

اگر تمام Weightها Non-negative هستند:

Code

Dijkstra

معمولاً سریع‌تر است.

اگر Graph بدون وزن است:

Code

BFS

بهتر است.

اگر Graph DAG است:

Code

Topological Order + Relaxation

می‌تواند O(V+E) باشد.

اگر All-Pairs می‌خواهیم:

Code

Floyd-Warshall
Johnson

بسته به Density و Weightها مطرح می‌شوند.

خطاهای رایج

1. اجرا فقط V-2 بار

در Worst Case ممکن است Shortest Path شامل V-1 Edge باشد.

2. فراموش کردن Pass اضافه برای Negative Cycle

بدون آن فقط Distance محاسبه می‌کنیم و Cycle منفی را Detect نمی‌کنیم.

3. گزارش هر Negative Cycle در Graph

Bellman-Ford Single Source فقط Cycleهای قابل‌دسترسی از Source را Detect می‌کند، مگر Super Source بسازیم.

4. استفاده از Bellman-Ford روی Graph بدون نیاز

اگر همه Weightها مثبت‌اند، هزینه O(VE) ممکن است بی‌دلیل زیاد باشد.

5. بازسازی Path بدون Parent

اگر Path واقعی لازم است، باید هنگام Relaxation Parent ذخیره شود.

6. استفاده روی Undirected Negative Edge بدون توجه

Undirected Negative Edge خودش Cycle منفی دوطرفه ایجاد می‌کند.

7. اشتباه گرفتن Negative Edge با Negative Cycle

وجود Edge منفی به‌تنهایی مشکل نیست.

مشکل وقتی است که مجموع Weightهای یک Cycle منفی باشد.

Negative Edge vs Negative Cycle

این تفاوت مهم است.

Negative Edge

کاملاً قابل مدیریت است.

Code

A → B = -5

به خودی خود مشکلی ندارد.

Negative Cycle

باعث می‌شود Shortest Path تعریف محدود نداشته باشد.

Code

A → B → C → A
total < 0

جدول تصمیم سریع

نوع مسئله	الگوریتم
Unweighted Shortest Path	BFS
Non-negative Weighted	Dijkstra
Negative Edge	Bellman-Ford
Detect Reachable Negative Cycle	Bellman-Ford
DAG with weights	Topological DP
All-Pairs Dense Graph	Floyd-Warshall
All-Pairs Sparse + Negative Edges	Johnson
0/1 weights	0-1 BFS

جمع‌بندی

Bellman-Ford یک الگوریتم Single-Source Shortest Path است که Edgeهای منفی را پشتیبانی می‌کند.

قلب الگوریتم:

Code

Relax every edge

است.

برای Graph با V Vertex:

Code

V - 1

بار تمام Edgeها Relax می‌شوند.

اگر بعد از آن هنوز Relaxation ممکن باشد:

Code

Negative Cycle reachable from source

وجود دارد.

Complexity:

Code

O(VE)

و فضای کمکی:

Code

O(V)

است.

مهم‌ترین تفاوت با Dijkstra:

Code

Bellman-Ford
→ negative weights allowed
→ negative cycle detection
→ slower

Dijkstra
→ non-negative weights
→ usually faster

Pattern تشخیص مسئله:

Code

Shortest Path تک‌مبدأ می‌خواهم؟
Weight منفی ممکن است وجود داشته باشد؟
Negative Cycle هم باید Detect شود؟

→ Bellman-Ford

اما اگر Graph ساده‌تر باشد، همیشه الگوریتم متناسب‌تر را انتخاب کنید؛ Bellman-Ford ابزار قدرتمندی است، نه انتخاب پیش‌فرض برای هر Shortest Path.

Bellman-Ford یکی از مهم‌ترین الگوریتم‌های Shortest Path است؛ مخصوصاً وقتی Graph دارای Edge با وزن منفی باشد.

برخلاف Dijkstra، Bellman-Ford می‌تواند با:

Code

negative edge weight

کار کند.

و حتی یک قابلیت مهم‌تر دارد:

اگر از Source بتوان به یک Negative Cycle رسید، Bellman-Ford می‌تواند آن را تشخیص دهد.

Bellman-Ford دقیقاً چه مسئله‌ای را حل می‌کند؟

فرض کنید یک Graph وزن‌دار داریم و می‌خواهیم Shortest Path را از یک Source به همه‌ی Vertexها پیدا کنیم.

مثلاً:

Code

A --4--> B
A --5--> C
B --(-2)--> C

اگر از A شروع کنیم:

مسیر مستقیم:

Code

A → C
cost = 5

اما مسیر:

Code

A → B → C

هزینه:

Code

4 + (-2) = 2

دارد.

پس Shortest Path واقعی:

Code

A → B → C

است.

وجود Edge منفی باعث می‌شود الگوریتم‌هایی مثل Dijkstra در حالت عمومی قابل اعتماد نباشند.

Weight منفی یعنی چه؟

وزن منفی الزاماً چیز غیرواقعی نیست.

می‌تواند مدل‌کننده‌ی:

تخفیف
Credit
سود
کاهش هزینه
Bonus
Offset
Penalty معکوس

باشد.

مثلاً:

Code

Transaction A → B = +10
Transaction B → C = -4

ممکن است یک Edge منفی کاملاً معنی‌دار باشد.

ایده اصلی Bellman-Ford

ایده اصلی بسیار ساده است:

تمام Edgeها را بارها Relax کن تا دیگر هیچ Distanceای بهتر نشود.

این الگوریتم برخلاف Dijkstra سعی نمی‌کند یک Vertex را زود Final کند.

بلکه اجازه می‌دهد اطلاعات Shortest Path در چند Pass روی Graph پخش شود.

Relaxation چیست؟

Relaxation قلب Bellman-Ford است.

برای Edge:

Code

u → v
weight = w

اگر:

Code

dist[u] + w < dist[v]

باشد، یعنی مسیر:

Code

source → ... → u → v

از بهترین مسیر فعلی به v کوتاه‌تر است.

پس:

Code

dist[v] = dist[u] + w

مثال Relaxation

فرض کنید:

Code

dist[A] = 0
dist[B] = Infinity

و Edge:

Code

A → B weight 5

داریم.

چون:

Code

0 + 5 < Infinity

پس:

Code

dist[B] = 5

حالا اگر بعداً مسیر بهتری پیدا شود:

Code

A → C = 2
C → B = 1

آنگاه:

Code

dist[B] = 3

می‌شود.

مقداردهی اولیه

در Single-Source Shortest Path:

Code

dist[source] = 0

و بقیه:

Code

Infinity

مثلاً:

Code

A = 0
B = ∞
C = ∞
D = ∞

چرا Infinity؟

چون هنوز هیچ مسیر شناخته‌شده‌ای به آن Node نداریم.

وقتی اولین مسیر پیدا شود، عدد واقعی از Infinity کوچک‌تر خواهد بود.

الگوریتم مرحله‌به‌مرحله

Bellman-Ford:

Distance مبدأ را صفر کن.
Distance بقیه را Infinity کن.
تمام Edgeها را Relax کن.
این کار را V - 1 بار تکرار کن.
یک Pass اضافه روی Edgeها انجام بده.
اگر هنوز Relaxation ممکن بود، Negative Cycle قابل‌دسترسی از Source وجود دارد.

چرا دقیقاً V-1 بار؟

این یکی از مهم‌ترین سؤال‌های مفهومی است.

در Graph با V رأس، یک Shortest Path ساده نمی‌تواند بیش از:

Code

V - 1

Edge داشته باشد.

چرا؟

اگر Path بیش از V-1 Edge داشته باشد، حتماً یک Vertex تکرار شده و Cycle داریم.

اگر Cycle وزن غیرمنفی داشته باشد، حذف آن Path را بدتر نمی‌کند.

اگر Cycle وزن منفی داشته باشد، اصلاً Shortest Path محدود و مشخص نداریم چون می‌توانیم Cycle را بارها تکرار کنیم.

پس برای Graph بدون Negative Cycle مؤثر:

Code

V - 1 relaxation rounds

کافی است.

نگاه دیگری به V-1 Pass

بعد از Pass اول، Shortest Pathهایی که حداکثر یک Edge دارند می‌توانند درست شوند.

بعد از Pass دوم:

Code

حداکثر 2 Edge

بعد از Pass سوم:

Code

حداکثر 3 Edge

و ...

بعد از:

Code

V - 1

Pass تمام Shortest Pathهای ساده پوشش داده شده‌اند.

پیاده‌سازی پایه JavaScript

JavaScript

function bellmanFord(vertices, edges, source) {
  const dist = Object.fromEntries(
    vertices.map(v => [v, Infinity])
  );

  dist[source] = 0;

  for (let i = 0; i < vertices.length - 1; i++) {
    for (const [u, v, w] of edges) {
      if (
        dist[u] !== Infinity &&
        dist[u] + w < dist[v]
      ) {
        dist[v] = dist[u] + w;
      }
    }
  }

  for (const [u, v, w] of edges) {
    if (
      dist[u] !== Infinity &&
      dist[u] + w < dist[v]
    ) {
      throw new Error(
        "Negative cycle reachable from source"
      );
    }
  }

  return dist;
}

چرا شرط dist[u] !== Infinity لازم است؟

اگر u از Source قابل دسترسی نباشد:

Code

dist[u] = Infinity

نباید Edgeهای خروجی آن را Relax کنیم.

در JavaScript:

Code

Infinity + (-5) = Infinity

است، ولی شرط صریح هم Intent را واضح می‌کند و هم منطق الگوریتم را درست نگه می‌دارد.

مثال کامل

Vertexها:

Code

A, B, C, D

Edgeها:

Code

A → B = 4
A → C = 5
B → C = -2
C → D = 3

ابتدا:

Code

A = 0
B = ∞
C = ∞
D = ∞

Pass اول

Edge:

Code

A → B = 4

پس:

Code

B = 4

Edge:

Code

A → C = 5

پس:

Code

C = 5

Edge:

Code

B → C = -2

داریم:

Code

4 + (-2) = 2

پس:

Code

C = 2

Edge:

Code

C → D = 3

پس:

Code

D = 5

نتیجه:

Code

A = 0
B = 4
C = 2
D = 5

آیا همیشه باید V-1 Pass کامل اجرا کنیم؟

نه.

اگر در یک Pass هیچ Distanceای Update نشود، الگوریتم Converge شده است.

می‌توانیم زود متوقف شویم.

Early Stop Optimization

JavaScript

function bellmanFordOptimized(
  vertices,
  edges,
  source
) {
  const dist = Object.fromEntries(
    vertices.map(v => [v, Infinity])
  );

  dist[source] = 0;

  for (let i = 0; i < vertices.length - 1; i++) {
    let updated = false;

    for (const [u, v, w] of edges) {
      if (
        dist[u] !== Infinity &&
        dist[u] + w < dist[v]
      ) {
        dist[v] = dist[u] + w;
        updated = true;
      }
    }

    if (!updated) {
      break;
    }
  }

  return dist;
}

در Worst Case همچنان:

Code

O(VE)

است، اما در بعضی Graphها زودتر تمام می‌شود.

Negative Cycle چیست؟

Cycleای است که مجموع Weightهایش منفی باشد.

مثلاً:

Code

A → B = 2
B → C = -5
C → A = 1

مجموع:

Code

2 - 5 + 1 = -2

پس Cycle وزن:

Code

-2

دارد.

چرا Negative Cycle مشکل ایجاد می‌کند؟

فرض کنید یک بار Cycle را طی کنیم:

Code

cost = -2

دو بار:

Code

cost = -4

سه بار:

Code

cost = -6

و همین‌طور:

Code

-∞

پس Shortest Path معنی مشخصی ندارد.

می‌توانیم هر بار با یک دور دیگر هزینه را کمتر کنیم.

تشخیص Negative Cycle

بعد از V-1 Pass، اگر Graph Negative Cycle قابل‌دسترسی نداشته باشد، هیچ Relaxation دیگری نباید ممکن باشد.

پس یک Pass اضافه می‌زنیم.

اگر هنوز:

Code

dist[u] + w < dist[v]

باشد:

Code

Negative Cycle exists

نکته بسیار مهم: Cycle باید از Source قابل دسترس باشد

فرض کنید Graph دو Component دارد.

Component اول Source در آن است.

Component دوم Negative Cycle دارد اما Source هیچ راهی به آن ندارد.

در Single-Source Bellman-Ford معمولاً آن Cycle روی Distanceهای Source تأثیری ندارد.

به همین دلیل شرط:

JavaScript

dist[u] !== Infinity

در Cycle Detection مهم است.

تشخیص وجود Negative Cycle در کل Graph

اگر بخواهیم بفهمیم هر جای Graph Negative Cycle وجود دارد، نه فقط Reachable از یک Source، می‌توانیم یک Super Source مجازی بسازیم.

به همه Vertexها Edge صفر بدهیم:

Code

S → v
weight = 0

برای همه v.

حالا تمام Graph از S قابل دسترسی است.

Super Source

مثلاً:

Code

S → A = 0
S → B = 0
S → C = 0
S → D = 0

بعد Bellman-Ford را از S اجرا می‌کنیم.

اگر Cycle منفی هر جایی وجود داشته باشد، قابل تشخیص می‌شود.

بازسازی Shortest Path

فقط Distance همیشه کافی نیست.

گاهی می‌خواهیم خود مسیر را هم بدانیم.

برای این کار هنگام Relaxation:

Code

parent[v] = u

ذخیره می‌کنیم.

Bellman-Ford با Parent

JavaScript

function bellmanFordWithPath(
  vertices,
  edges,
  source
) {
  const dist = Object.fromEntries(
    vertices.map(v => [v, Infinity])
  );

  const parent = Object.fromEntries(
    vertices.map(v => [v, null])
  );

  dist[source] = 0;

  for (let i = 0; i < vertices.length - 1; i++) {
    let updated = false;

    for (const [u, v, w] of edges) {
      if (
        dist[u] !== Infinity &&
        dist[u] + w < dist[v]
      ) {
        dist[v] = dist[u] + w;
        parent[v] = u;
        updated = true;
      }
    }

    if (!updated) {
      break;
    }
  }

  return {
    dist,
    parent
  };
}

بازسازی مسیر

JavaScript

function buildPath(parent, source, target) {
  const path = [];

  let current = target;

  while (current !== null) {
    path.push(current);

    if (current === source) {
      return path.reverse();
    }

    current = parent[current];
  }

  return null;
}

اگر Target reachable نباشد:

Code

null

برمی‌گردد.

پیدا کردن خود Negative Cycle

گاهی فقط دانستن:

Code

negative cycle exists

کافی نیست.

مثلاً در Debugging یا Arbitrage Analysis می‌خواهیم Cycle را ببینیم.

یک تکنیک معروف:

در Pass اضافه، آخرین Vertex Update‌شده را ذخیره کن.
از Parent آن Vertex، V بار عقب برو.
حالا حتماً داخل Cycle قرار گرفته‌ای.
Parentها را ادامه بده تا دوباره به همان Vertex برگردی.

ایده بازسازی Negative Cycle

اگر Vertex:

Code

در Pass شماره V Update شود، می‌دانیم تحت تأثیر Negative Cycle قرار گرفته است.

با:

Code

x = parent[x]

به تعداد V بار، Prefix خارج Cycle را حذف می‌کنیم.

بعد Cycle را بازسازی می‌کنیم.

Bellman-Ford vs Dijkstra

این مقایسه بسیار مهم است.

ویژگی	Bellman-Ford	Dijkstra
Negative Edge	بله	خیر، در حالت استاندارد
Negative Cycle Detection	بله	خیر
Complexity	O(VE)	معمولاً O((V+E) log V)
سرعت	کندتر	سریع‌تر
Relaxation	همه Edgeها چندبار	Greedy + Priority Queue
کاربرد اصلی	وزن منفی / cycle detection	وزن غیرمنفی

چرا Dijkstra با وزن منفی مشکل دارد؟

Dijkstra فرض می‌کند وقتی نزدیک‌ترین Vertex را Final کردیم، بعداً Path بهتری پیدا نمی‌شود.

Negative Edge می‌تواند این فرض را بشکند.

مثلاً ممکن است Vertexای زود Final شود ولی بعداً از یک مسیر با Edge منفی Distance بهتری به آن برسد.

Bellman-Ford چنین Finalization زودهنگامی ندارد.

BFS vs Bellman-Ford

اگر Graph بدون وزن باشد:

Code

BFS

بهتر است.

اگر تمام Weightها برابر باشند:

Code

BFS

معمولاً کافی است.

اگر Weightها متفاوت و ممکن است منفی باشند:

Code

Bellman-Ford

مطرح می‌شود.

DAG Shortest Path vs Bellman-Ford

اگر Graph یک DAG باشد، حتی با Weight منفی می‌توان:

Topological Sort گرفت.
Edgeها را در Topological Order Relax کرد.

Complexity:

Code

O(V + E)

که بسیار بهتر از:

Code

O(VE)

است.

پس اگر Graph DAG است، Bellman-Ford لزوماً بهترین گزینه نیست.

Floyd-Warshall vs Bellman-Ford

Bellman-Ford

Single Source:

Code

source → all vertices

Floyd-Warshall

All Pairs:

Code

every vertex → every vertex

Complexity Floyd-Warshall:

Code

O(V³)

پس سؤال مهم این است:

Code

Single Source?
یا
All Pairs?

Johnson's Algorithm

برای All-Pairs Shortest Path در Sparse Graph با Weight منفی ولی بدون Negative Cycle، الگوریتم Johnson مهم است.

Johnson از Bellman-Ford برای Reweight کردن Edgeها استفاده می‌کند و سپس Dijkstra را از هر Vertex اجرا می‌کند.

این نشان می‌دهد Bellman-Ford پایه‌ی الگوریتم‌های پیشرفته‌تر نیز هست.

کاربرد: Distance Vector Routing

Bellman-Ford از نظر مفهومی پایه‌ی الگوریتم‌های Distance Vector Routing است.

هر Router اطلاعات Distance خود را از Neighborها دریافت می‌کند و می‌پرسد:

Code

اگر از Neighbor X بروم،
آیا Route به Destination ارزان‌تر می‌شود؟

این دقیقاً شبیه Relaxation است.

Routing Table

فرم مفهومی:

Code

distance(destination)
=
min over neighbors(
  cost(to neighbor)
  +
  neighbor distance(destination)
)

این همان Dynamic Programming / Bellman equation است.

مشکل Count-to-Infinity

Distance Vector Routing مشکلاتی مثل:

Code

count-to-infinity

دارد.

وقتی Route خراب می‌شود، Routerها ممکن است اطلاعات اشتباه را بین خود پخش کنند و Metric به‌تدریج افزایش پیدا کند.

راهکارهایی مثل:

Split Horizon
Poison Reverse
Hold-down

در Protocolهای Routing مطرح می‌شوند.

پس Bellman-Ford در دنیای Networking فقط یک الگوریتم تئوری نیست.

مدل سود و زیان

فرض کنید Edge Weight نشان‌دهنده Cost باشد.

Negative Weight می‌تواند Discount یا Credit باشد.

مثلاً:

Code

Supplier A → B = +10
B → C = -4

Bellman-Ford می‌تواند Minimum Net Cost را پیدا کند.

Arbitrage و Negative Cycle

در مسائل Currency Arbitrage می‌توان Rateها را با Transformation لگاریتمی به Weight تبدیل کرد.

اگر Cycle مناسب با وزن منفی پیدا شود، می‌تواند نشان‌دهنده فرصت Arbitrage در مدل ریاضی باشد.

البته در بازار واقعی:

fee
spread
liquidity
slippage
timing

هم مهم‌اند.

Credit/Penalty Graph

در بعضی سیستم‌ها Edgeها می‌توانند:

penalty مثبت
credit منفی

داشته باشند.

Bellman-Ford برای چنین Cost Modelهایی طبیعی است.

Constraint Systems

بعضی Difference Constraintها به فرم:

Code

x_v <= x_u + w

هستند.

این Relation دقیقاً شبیه Relaxation Bellman-Ford است.

Negative Cycle می‌تواند نشانه‌ی ناسازگار بودن Constraintها باشد.

Difference Constraints

اگر Constraintها را به Edge تبدیل کنیم:

Code

u → v weight w

Bellman-Ford می‌تواند feasibility سیستم را بررسی کند.

این یکی از کاربردهای نظری و عملی مهم الگوریتم است.

Edge List چرا مناسب Bellman-Ford است؟

Bellman-Ford در هر Pass باید:

Code

all edges

را بررسی کند.

پس Representation طبیعی:

JavaScript

[
  [u, v, w],
  [u, v, w],
  ...
]

است.

Adjacency List هم ممکن است، ولی Edge List ساده‌تر است.

Directed و Undirected Graph

Bellman-Ford برای Directed Graph طبیعی است.

برای Undirected Graph، هر Edge:

Code

u -- v weight w

را می‌توان به دو Directed Edge تبدیل کرد:

Code

u → v weight w
v → u weight w

اما یک نکته مهم وجود دارد.

Weight منفی در Undirected Graph

اگر یک Undirected Edge وزن منفی داشته باشد:

Code

u -- v = -5

معادل دو Edge:

Code

u → v = -5
v → u = -5

است.

پس Cycle:

Code

u → v → u

وزن:

Code

-10

دارد.

بنابراین یک Undirected Negative Edge عملاً Negative Cycle ایجاد می‌کند.

این نکته در مدل‌سازی بسیار مهم است.

Unreachable Vertices

اگر Vertex از Source قابل دسترسی نباشد:

Code

dist[v] = Infinity

باقی می‌ماند.

این Error نیست؛ یعنی Path وجود ندارد.

Empty Graph

اگر Graph Vertex نداشته باشد، باید Source هم وجود نداشته باشد یا Validation انجام شود.

Source نامعتبر

در Production بهتر است بررسی کنیم:

Code

source ∈ vertices

اگر Source در Vertexها نیست، Error واضح برگردانیم.

Duplicate Edges

وجود چند Edge از u به v مشکلی ندارد.

Bellman-Ford همه را Relax می‌کند و بهترین گزینه مؤثر خواهد شد.

Self-loop

Self-loop:

Code

u → u

اگر Weight آن منفی باشد:

Code

negative self-cycle

است.

مثلاً:

Code

u → u = -1

یک Negative Cycle واضح است.

Overflow و Infinity

در زبان‌هایی با Integer محدود باید مراقب Overflow باشیم.

در JavaScript Number از Floating Point استفاده می‌کند، اما باز هم:

Infinity
very large values
precision limits

باید در مدل‌های بزرگ در نظر گرفته شوند.

نسخه کامل‌تر با Result Object

در Production بهتر است به جای throw کردن، Result ساختاری برگردانیم.

JavaScript

function bellmanFordSafe(
  vertices,
  edges,
  source
) {
  const dist = new Map();
  const parent = new Map();

  for (const v of vertices) {
    dist.set(v, Infinity);
    parent.set(v, null);
  }

  if (!dist.has(source)) {
    return {
      ok: false,
      reason: "INVALID_SOURCE"
    };
  }

  dist.set(source, 0);

  for (let i = 0; i < vertices.length - 1; i++) {
    let updated = false;

    for (const [u, v, w] of edges) {
      const du = dist.get(u);
      const dv = dist.get(v);

      if (
        du !== Infinity &&
        du + w < dv
      ) {
        dist.set(v, du + w);
        parent.set(v, u);
        updated = true;
      }
    }

    if (!updated) {
      break;
    }
  }

  for (const [u, v, w] of edges) {
    const du = dist.get(u);
    const dv = dist.get(v);

    if (
      du !== Infinity &&
      du + w < dv
    ) {
      return {
        ok: false,
        reason: "NEGATIVE_CYCLE",
        dist,
        parent
      };
    }
  }

  return {
    ok: true,
    dist,
    parent
  };
}

TypeScript Version

TypeScript

type Vertex = string;

type Edge = [
  from: Vertex,
  to: Vertex,
  weight: number
];

type BellmanFordResult =
  | {
      ok: true;
      dist: Map<Vertex, number>;
      parent: Map<Vertex, Vertex | null>;
    }
  | {
      ok: false;
      reason: "INVALID_SOURCE" | "NEGATIVE_CYCLE";
      dist?: Map<Vertex, number>;
      parent?: Map<Vertex, Vertex | null>;
    };

function bellmanFord(
  vertices: Vertex[],
  edges: Edge[],
  source: Vertex
): BellmanFordResult {
  const dist = new Map<Vertex, number>();
  const parent =
    new Map<Vertex, Vertex | null>();

  for (const v of vertices) {
    dist.set(v, Infinity);
    parent.set(v, null);
  }

  if (!dist.has(source)) {
    return {
      ok: false,
      reason: "INVALID_SOURCE"
    };
  }

  dist.set(source, 0);

  for (
    let i = 0;
    i < vertices.length - 1;
    i++
  ) {
    let updated = false;

    for (const [u, v, w] of edges) {
      const du = dist.get(u)!;
      const dv = dist.get(v)!;

      if (
        du !== Infinity &&
        du + w < dv
      ) {
        dist.set(v, du + w);
        parent.set(v, u);
        updated = true;
      }
    }

    if (!updated) {
      break;
    }
  }

  for (const [u, v, w] of edges) {
    const du = dist.get(u)!;
    const dv = dist.get(v)!;

    if (
      du !== Infinity &&
      du + w < dv
    ) {
      return {
        ok: false,
        reason: "NEGATIVE_CYCLE",
        dist,
        parent
      };
    }
  }

  return {
    ok: true,
    dist,
    parent
  };
}

پیچیدگی زمانی

Bellman-Ford:

Code

V - 1

Pass دارد.

در هر Pass:

Code

Edge بررسی می‌شود.

پس:

Code

Time = O(VE)

پیچیدگی فضایی

برای:

dist
parent

تقریباً:

Code

O(V)

فضای کمکی نیاز داریم.

خود Edge List:

Code

O(E)

فضا دارد.

چه زمانی Bellman-Ford استفاده کنیم؟

وقتی:

Negative Edge داریم.
Negative Cycle Detection لازم است.
Single-Source Shortest Path می‌خواهیم.
Difference Constraints داریم.
Distance Vector logic داریم.
Cost Model شامل Credit/Penalty است.
Dijkstra به دلیل Weight منفی قابل استفاده نیست.

چه زمانی Bellman-Ford بهترین انتخاب نیست؟

اگر تمام Weightها Non-negative هستند:

Code

Dijkstra

معمولاً سریع‌تر است.

اگر Graph بدون وزن است:

Code

BFS

بهتر است.

اگر Graph DAG است:

Code

Topological Order + Relaxation

می‌تواند O(V+E) باشد.

اگر All-Pairs می‌خواهیم:

Code

Floyd-Warshall
Johnson

بسته به Density و Weightها مطرح می‌شوند.

خطاهای رایج

1. اجرا فقط V-2 بار

در Worst Case ممکن است Shortest Path شامل V-1 Edge باشد.

2. فراموش کردن Pass اضافه برای Negative Cycle

بدون آن فقط Distance محاسبه می‌کنیم و Cycle منفی را Detect نمی‌کنیم.

3. گزارش هر Negative Cycle در Graph

Bellman-Ford Single Source فقط Cycleهای قابل‌دسترسی از Source را Detect می‌کند، مگر Super Source بسازیم.

4. استفاده از Bellman-Ford روی Graph بدون نیاز

اگر همه Weightها مثبت‌اند، هزینه O(VE) ممکن است بی‌دلیل زیاد باشد.

5. بازسازی Path بدون Parent

اگر Path واقعی لازم است، باید هنگام Relaxation Parent ذخیره شود.

6. استفاده روی Undirected Negative Edge بدون توجه

Undirected Negative Edge خودش Cycle منفی دوطرفه ایجاد می‌کند.

7. اشتباه گرفتن Negative Edge با Negative Cycle

وجود Edge منفی به‌تنهایی مشکل نیست.

مشکل وقتی است که مجموع Weightهای یک Cycle منفی باشد.

Negative Edge vs Negative Cycle

این تفاوت مهم است.

Negative Edge

کاملاً قابل مدیریت است.

Code

A → B = -5

به خودی خود مشکلی ندارد.

Negative Cycle

باعث می‌شود Shortest Path تعریف محدود نداشته باشد.

Code

A → B → C → A
total < 0

جدول تصمیم سریع

نوع مسئله	الگوریتم
Unweighted Shortest Path	BFS
Non-negative Weighted	Dijkstra
Negative Edge	Bellman-Ford
Detect Reachable Negative Cycle	Bellman-Ford
DAG with weights	Topological DP
All-Pairs Dense Graph	Floyd-Warshall
All-Pairs Sparse + Negative Edges	Johnson
0/1 weights	0-1 BFS

جمع‌بندی

Bellman-Ford یک الگوریتم Single-Source Shortest Path است که Edgeهای منفی را پشتیبانی می‌کند.

قلب الگوریتم:

Code

Relax every edge

است.

برای Graph با V Vertex:

Code

V - 1

بار تمام Edgeها Relax می‌شوند.

اگر بعد از آن هنوز Relaxation ممکن باشد:

Code

Negative Cycle reachable from source

وجود دارد.

Complexity:

Code

O(VE)

و فضای کمکی:

Code

O(V)

است.

مهم‌ترین تفاوت با Dijkstra:

Code

Bellman-Ford
→ negative weights allowed
→ negative cycle detection
→ slower

Dijkstra
→ non-negative weights
→ usually faster

Pattern تشخیص مسئله:

Code

Shortest Path تک‌مبدأ می‌خواهم؟
Weight منفی ممکن است وجود داشته باشد؟
Negative Cycle هم باید Detect شود؟

→ Bellman-Ford

الگوریتم Bellman-Ford چیست؟ کوتاه‌ترین مسیر با وزن منفی

Bellman-Ford دقیقاً چه مسئله‌ای را حل می‌کند؟

Weight منفی یعنی چه؟

ایده اصلی Bellman-Ford

Relaxation چیست؟

مثال Relaxation

مقداردهی اولیه

چرا Infinity؟

الگوریتم مرحله‌به‌مرحله

چرا دقیقاً V-1 بار؟

نگاه دیگری به V-1 Pass

پیاده‌سازی پایه JavaScript

چرا شرط dist[u] !== Infinity لازم است؟

مثال کامل

Pass اول

آیا همیشه باید V-1 Pass کامل اجرا کنیم؟

Early Stop Optimization

Negative Cycle چیست؟

چرا Negative Cycle مشکل ایجاد می‌کند؟

تشخیص Negative Cycle

نکته بسیار مهم: Cycle باید از Source قابل دسترس باشد

تشخیص وجود Negative Cycle در کل Graph

Super Source

بازسازی Shortest Path

Bellman-Ford با Parent

بازسازی مسیر

پیدا کردن خود Negative Cycle

ایده بازسازی Negative Cycle

Bellman-Ford vs Dijkstra

چرا Dijkstra با وزن منفی مشکل دارد؟

BFS vs Bellman-Ford

DAG Shortest Path vs Bellman-Ford

Floyd-Warshall vs Bellman-Ford

Bellman-Ford

Floyd-Warshall

Johnson's Algorithm

کاربرد: Distance Vector Routing

Routing Table

مشکل Count-to-Infinity

مدل سود و زیان

Arbitrage و Negative Cycle

Credit/Penalty Graph

Constraint Systems

Difference Constraints

Edge List چرا مناسب Bellman-Ford است؟

Directed و Undirected Graph

Weight منفی در Undirected Graph

Unreachable Vertices

Empty Graph

Source نامعتبر

Duplicate Edges

Self-loop

Overflow و Infinity

نسخه کامل‌تر با Result Object

TypeScript Version

پیچیدگی زمانی

پیچیدگی فضایی

چه زمانی Bellman-Ford استفاده کنیم؟

چه زمانی Bellman-Ford بهترین انتخاب نیست؟

خطاهای رایج

1. اجرا فقط V-2 بار

2. فراموش کردن Pass اضافه برای Negative Cycle

3. گزارش هر Negative Cycle در Graph

4. استفاده از Bellman-Ford روی Graph بدون نیاز

5. بازسازی Path بدون Parent

6. استفاده روی Undirected Negative Edge بدون توجه

7. اشتباه گرفتن Negative Edge با Negative Cycle

Negative Edge vs Negative Cycle

Negative Edge

Negative Cycle

جدول تصمیم سریع

جمع‌بندی

Bridge در گراف چیست؟ پیدا کردن یال‌های بحرانی شبکه

Floyd-Warshall چیست؟ کوتاه‌ترین مسیر بین تمام جفت رأس‌ها

الگوریتم Bellman-Ford چیست؟ کوتاه‌ترین مسیر با وزن منفی

Bellman-Ford دقیقاً چه مسئله‌ای را حل می‌کند؟

Weight منفی یعنی چه؟

ایده اصلی Bellman-Ford

Relaxation چیست؟

مثال Relaxation