Floyd-Warshall یکی از مهم‌ترین الگوریتم‌های کلاسیک برای حل مسئله‌ی All-Pairs Shortest Paths است.

یعنی به‌جای اینکه فقط از یک Source به بقیه‌ی Nodeها Shortest Path پیدا کنیم، می‌خواهیم بدانیم:

Code

Shortest Path بین هر i و هر j چقدر است؟

مثلاً اگر Graph شامل شهرها باشد، خروجی الگوریتم می‌تواند یک Matrix باشد که فاصله‌ی کوتاه‌ترین مسیر بین هر دو شهر را نشان می‌دهد.

این الگوریتم بر پایه‌ی Dynamic Programming ساخته شده و ایده‌ی آن بسیار ساده اما قدرتمند است:

برای هر Vertex واسطه‌ی k بررسی کن آیا رفتن از i به j از طریق k بهتر از مسیر فعلی است یا نه.

در این مقاله Floyd-Warshall را از صفر بررسی می‌کنیم؛ از ماتریس فاصله و DP State گرفته تا Path Reconstruction، Negative Edge، Negative Cycle، Transitive Closure، مقایسه با Dijkstra و Bellman-Ford و پیاده‌سازی کامل JavaScript و TypeScript.

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

فرض کنید Graph زیر را داریم:

Code

A --3--> B
A --10-> C
B --4--> C

مسیر مستقیم:

Code

A → C
cost = 10

اما مسیر:

Code

A → B → C
cost = 3 + 4 = 7

بهتر است.

پس:

Code

dist[A][C] = 7

Floyd-Warshall این کار را برای تمام جفت رأس‌ها انجام می‌دهد.

Single-Source vs All-Pairs

Single-Source Shortest Path

مثلاً:

Code

A → همه Nodeها

الگوریتم‌های رایج:

BFS
Dijkstra
Bellman-Ford

All-Pairs Shortest Path

مثلاً:

Code

A → همه
B → همه
C → همه
...

Floyd-Warshall مستقیماً این Matrix را محاسبه می‌کند.

ایده‌ی اصلی به ساده‌ترین شکل

فرض کنید می‌خواهیم Shortest Path بین i و j را پیدا کنیم.

برای یک Vertex واسطه‌ی k دو انتخاب داریم:

Code

1. مسیر فعلی i → j
2. مسیر i → k → j

پس:

Code

dist[i][j]
=
min(
  dist[i][j],
  dist[i][k] + dist[k][j]
)

این همان قلب Floyd-Warshall است.

چرا این Dynamic Programming است؟

فرض کنید:

Code

D_k[i][j]

یعنی کوتاه‌ترین مسیر از i به j با این محدودیت که فقط Vertexهای:

Code

0 ... k

اجازه دارند به‌عنوان Intermediate Vertex استفاده شوند.

برای Vertex جدید k:

Code

D_k[i][j]
=
min(
  D_{k-1}[i][j],
  D_{k-1}[i][k] + D_{k-1}[k][j]
)

یعنی:

یا مسیر بهینه از k عبور نمی‌کند،
یا از k عبور می‌کند.

این یک recurrence کلاسیک Dynamic Programming است.

Matrix اولیه

فرض کنید Nodeها:

Code

A, B, C

باشند.

Graph:

Code

A → B = 3
B → C = 4
A → C = 10

Matrix اولیه:

Code

      A    B    C
A     0    3   10
B     ∞    0    4
C     ∞    ∞    0

چرا قطر اصلی صفر است؟

Distance هر Node به خودش بدون حرکت:

Code

است.

پس:

Code

dist[i][i] = 0

البته اگر Negative Cycle وجود داشته باشد، بعداً ممکن است:

Code

dist[i][i] < 0

شود.

این نکته برای Negative Cycle Detection بسیار مهم است.

چرا Infinity استفاده می‌کنیم؟

اگر Edge مستقیمی از i به j وجود نداشته باشد:

Code

dist[i][j] = Infinity

یعنی هنوز هیچ Path شناخته‌شده‌ای نداریم.

الگوریتم اصلی

JavaScript

function floydWarshall(matrix) {
  const dist = matrix.map(row => [...row]);
  const n = dist.length;

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        dist[i][j] = Math.min(
          dist[i][j],
          dist[i][k] + dist[k][j]
        );
      }
    }
  }

  return dist;
}

چرا k باید حلقه بیرونی باشد؟

این یکی از مهم‌ترین نکات Floyd-Warshall است.

Code

نماینده‌ی مجموعه‌ی Intermediate Vertexهایی است که تا این مرحله اجازه‌ی استفاده از آن‌ها را داده‌ایم.

پس باید ابتدا یک k را ثابت کنیم و سپس تمام i, jها را با اجازه‌ی استفاده از آن Update کنیم.

ترتیب:

Code

for k
  for i
    for j

مفهوم DP را حفظ می‌کند.

اگر Loopها را بی‌دقت جابه‌جا کنیم، ممکن است Stateهایی را در زمانی استفاده کنیم که هنوز طبق تعریف DP مجاز نیستند.

مثال مرحله‌به‌مرحله

Matrix اولیه:

Code

      A    B    C
A     0    3   10
B     ∞    0    4
C     ∞    ∞    0

وقتی:

Code

k = B

مسیر A تا C از طریق B بررسی می‌شود:

Code

dist[A][B] + dist[B][C]
=
3 + 4
=
7

چون:

Code

7 < 10

پس:

Code

dist[A][C] = 7

Matrix نهایی:

Code

      A    B    C
A     0    3    7
B     ∞    0    4
C     ∞    ∞    0

Floyd-Warshall روی Graph جهت‌دار

الگوریتم برای Directed Graph کاملاً طبیعی است.

Matrix لزوماً symmetric نیست.

مثلاً:

Code

dist[A][B] = 3

ولی ممکن است:

Code

dist[B][A] = Infinity

باشد.

Floyd-Warshall روی Graph بدون‌جهت

برای Undirected Graph، Edge:

Code

A -- B = 5

در Matrix:

Code

dist[A][B] = 5
dist[B][A] = 5

ثبت می‌شود.

آیا Negative Edge پشتیبانی می‌شود؟

بله.

Floyd-Warshall می‌تواند Edgeهای با Weight منفی داشته باشد، به شرط اینکه Shortest Path موردنظر تحت تأثیر Negative Cycle نباشد.

مثلاً:

Code

A → B = 4
B → C = -2
A → C = 10

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

Negative Cycle چیست؟

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

مثلاً:

Code

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

مجموع:

Code

2 - 5 + 1 = -2

پس Negative Cycle داریم.

چرا Negative Cycle Shortest Path را خراب می‌کند؟

اگر یک بار Cycle را طی کنیم:

Code

cost = -2

دو بار:

Code

-4

و همین‌طور:

Code

-∞

پس برای Vertexهایی که می‌توانند وارد این Cycle شوند و از آن به مقصد برسند، Shortest Path محدود و مشخصی نداریم.

تشخیص Negative Cycle با Floyd-Warshall

بعد از پایان الگوریتم، قطر اصلی Matrix را بررسی می‌کنیم.

اگر برای Vertexای:

Code

dist[i][i] < 0

باشد، Negative Cycle وجود دارد.

چرا؟

چون مسیر از i به خودش با Cost منفی پیدا شده است.

JavaScript Negative Cycle Detection

JavaScript

function hasNegativeCycle(dist) {
  for (let i = 0; i < dist.length; i++) {
    if (dist[i][i] < 0) {
      return true;
    }
  }

  return false;
}

نکته مهم درباره‌ی Negative Cycle

وجود Negative Cycle در Graph به این معنی نیست که تمام Pairها جواب نامعتبر دارند.

فقط Pairهایی که:

می‌توانند به Negative Cycle برسند،
و از آن Cycle به Destination برسند،

تحت تأثیر قرار می‌گیرند.

علامت‌گذاری Pairهای تحت تأثیر Negative Cycle

اگر:

Code

dist[i][k] !== Infinity
dist[k][k] < 0
dist[k][j] !== Infinity

باشد، Path از i به j می‌تواند از Negative Cycle عبور کند.

در این حالت می‌توان Distance را مفهومی به:

Code

-Infinity

تبدیل کرد.

نمونه

JavaScript

function markNegativeInfinity(dist) {
  const n = dist.length;

  for (let k = 0; k < n; k++) {
    if (dist[k][k] >= 0) continue;

    for (let i = 0; i < n; i++) {
      if (dist[i][k] === Infinity) continue;

      for (let j = 0; j < n; j++) {
        if (dist[k][j] === Infinity) continue;

        dist[i][j] = -Infinity;
      }
    }
  }

  return dist;
}

Path Reconstruction

گاهی Matrix فاصله کافی نیست.

می‌خواهیم بدانیم:

Code

A → B → D → F

مسیر واقعی چیست.

برای این کار یک Matrix دیگر نگه می‌داریم:

Code

next[i][j]

next Matrix چیست؟

اگر Edge مستقیم i → j وجود دارد:

Code

next[i][j] = j

وقتی Path بهتر از طریق k پیدا شود:

Code

next[i][j] = next[i][k]

یعنی اولین Step از i به سمت j همان اولین Step در مسیر i به k است.

Floyd-Warshall با Path Reconstruction

JavaScript

function floydWarshallWithPath(matrix) {
  const n = matrix.length;

  const dist = matrix.map(row => [...row]);

  const next = Array.from(
    { length: n },
    () => Array(n).fill(null)
  );

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (
        i !== j &&
        dist[i][j] !== Infinity
      ) {
        next[i][j] = j;
      }
    }
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        const throughK =
          dist[i][k] + dist[k][j];

        if (throughK < dist[i][j]) {
          dist[i][j] = throughK;
          next[i][j] = next[i][k];
        }
      }
    }
  }

  return {
    dist,
    next
  };
}

بازسازی مسیر

JavaScript

function reconstructPath(
  next,
  from,
  to
) {
  if (next[from][to] === null) {
    return null;
  }

  const path = [from];

  while (from !== to) {
    from = next[from][to];

    if (from === null) {
      return null;
    }

    path.push(from);
  }

  return path;
}

مثال Path Reconstruction

اگر Indexها:

Code

0 = A
1 = B
2 = C

و:

Code

next[0][2] = 1

باشد، یعنی Shortest Path از A به C ابتدا به B می‌رود.

Floyd-Warshall و Reachability

همین ساختار الگوریتم را می‌توان برای Reachability استفاده کرد.

به‌جای Distance از Boolean استفاده می‌کنیم.

قانون:

Code

reachable[i][j]
=
reachable[i][j]
OR
(
  reachable[i][k]
  AND
  reachable[k][j]
)

Transitive Closure

خروجی Boolean All-Pairs Reachability را معمولاً:

Code

Transitive Closure

می‌نامند.

Warshall Algorithm

نسخه Boolean الگوریتم معمولاً به نام:

Code

Warshall's Algorithm

شناخته می‌شود.

JavaScript برای Reachability

JavaScript

function transitiveClosure(matrix) {
  const reach = matrix.map(
    row => [...row]
  );

  const n = reach.length;

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        reach[i][j] =
          reach[i][j] ||
          (
            reach[i][k] &&
            reach[k][j]
          );
      }
    }
  }

  return reach;
}

کاربرد Reachability Matrix

مثلاً:

Dependency analysis
Permission propagation
Course prerequisite closure
Service reachability
Workflow reachability
Network connectivity queries

Floyd-Warshall vs Dijkstra

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

Floyd-Warshall

Code

All-Pairs
O(V³)

Dijkstra

یک بار:

Code

Single Source

اگر از هر Vertex اجرا شود:

Code

V × Dijkstra

Complexity با Heap تقریباً:

Code

O(V(E + V) log V)

در Sparse Graph ممکن است بهتر از Floyd-Warshall باشد.

چه زمانی Floyd-Warshall بهتر است؟

وقتی:

V نسبتاً کوچک یا متوسط است.
Graph Dense است.
All-Pairs Query زیاد داریم.
Matrix Representation طبیعی است.
Negative Edge داریم ولی Negative Cycle مؤثر نداریم.
سادگی Implementation مهم است.

چه زمانی Dijkstraهای تکراری بهترند؟

وقتی:

Graph Sparse است.
Weightها Non-negative هستند.
V بزرگ‌تر است.
فقط از تعدادی Source محدود Query داریم.

Floyd-Warshall vs Bellman-Ford

Bellman-Ford

Code

Single Source
O(VE)

پشتیبانی:

Negative Edge
Negative Cycle Detection

Floyd-Warshall

Code

All Pairs
O(V³)

پشتیبانی:

Negative Edge
Negative Cycle Detection از diagonal

Floyd-Warshall vs Johnson

Johnson برای:

Code

All-Pairs Shortest Path

روی Graph Sparse مناسب است.

روش:

Bellman-Ford
Reweight
Dijkstra از هر Vertex

برای Graph Sparse بزرگ، Johnson ممکن است بهتر از Floyd-Warshall باشد.

Floyd-Warshall vs BFS

اگر Graph Unweighted باشد و All-Pairs Distance بخواهیم، می‌توانیم BFS را از هر Vertex اجرا کنیم.

در Sparse Graph:

Code

O(V(V + E))

ممکن است بهتر از:

Code

O(V³)

باشد.

چرا Floyd-Warshall برای Graph Dense مناسب است؟

در Dense Graph:

Code

E ≈ V²

روش‌های مبتنی بر Edge هم به Complexity بالا نزدیک می‌شوند.

در چنین شرایطی Matrix و O(V³) می‌تواند انتخاب ساده و منطقی باشد.

کاربرد: Routing Matrix

فرض کنید یک Network کوچک یا متوسط داریم و می‌خواهیم بین تمام Nodeها Shortest Cost را Precompute کنیم.

Matrix نهایی:

Code

dist[i][j]

می‌تواند مستقیماً برای Queryهای بعدی استفاده شود.

کاربرد: Logistics

اگر تعداد Hubها محدود باشد:

Code

Hub 1
Hub 2
Hub 3
...

می‌توان Distance Matrix کامل را Precompute کرد.

بعد Query:

Code

cost(A, B)

در:

Code

O(1)

پاسخ داده می‌شود.

کاربرد: شعب و انبارها

اگر شرکت چند ده یا چند صد Branch/Depot داشته باشد، ممکن است All-Pairs Distance Matrix برای Planning مفید باشد.

البته در سیستم واقعی Road Network بسیار بزرگ، معمولاً الگوریتم‌های تخصصی‌تر استفاده می‌شوند.

کاربرد: Dependency Graph

اگر Edge Weight معنای Cost داشته باشد، می‌توان Cost بین همه Moduleها یا Stateها را محاسبه کرد.

اگر فقط Reachability مهم باشد، Transitive Closure مناسب‌تر است.

کاربرد: Game Map کوچک

در Game با تعداد State/Region محدود، می‌توان همه فاصله‌ها را Precompute کرد.

بعد AI می‌تواند Queryهای Distance را بسیار سریع جواب دهد.

کاربرد: Network Latency Matrix

اگر Nodeها محدود باشند و Edge Weight = latency باشد، Floyd-Warshall می‌تواند کمترین Latency نظری بین همه Pairها را محاسبه کند.

Dynamic Programming View

State اصلی:

Code

dist[i][j]

و Transition:

Code

dist[i][j]
=
min(
  dist[i][j],
  dist[i][k] + dist[k][j]
)

این یکی از شفاف‌ترین مثال‌های DP روی Graph است.

In-Place DP چرا کار می‌کند؟

به‌جای ساختن Matrix جدا برای هر k، همان Matrix را Update می‌کنیم.

این کار درست است چون در مرحله‌ی k فقط اطلاعاتی استفاده می‌کنیم که Intermediate Vertexهای مجازشان حداکثر k هستند.

این باعث کاهش Memory از:

Code

O(V³)

به:

Code

O(V²)

می‌شود.

Complexity زمانی

سه Loop داریم:

Code

k
i
j

هرکدام تا V.

پس:

Code

Time = O(V³)

Complexity فضایی

Matrix فاصله:

Code

V × V

است.

پس:

Code

Space = O(V²)

اگر Path Reconstruction هم بخواهیم:

Code

next matrix = O(V²)

و همچنان Big-O:

Code

O(V²)

می‌ماند.

آیا می‌توان Space را کمتر کرد؟

برای خروجی کامل All-Pairs Distance خودمان به Matrix:

Code

O(V²)

نیاز داریم.

پس کاهش چشمگیر Space معمولاً ممکن نیست اگر تمام جواب‌ها را همزمان بخواهیم.

Infinity Handling

در JavaScript:

Code

Infinity + number = Infinity

است.

اما برای خوانایی و کنترل بهتر می‌توان قبل از Transition بررسی کرد:

JavaScript

if (
  dist[i][k] === Infinity ||
  dist[k][j] === Infinity
) {
  continue;
}

نسخه Optimized‌تر از نظر محاسبات بی‌فایده

JavaScript

function floydWarshall(matrix) {
  const dist = matrix.map(
    row => [...row]
  );

  const n = dist.length;

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (dist[i][k] === Infinity) {
        continue;
      }

      for (let j = 0; j < n; j++) {
        if (dist[k][j] === Infinity) {
          continue;
        }

        const candidate =
          dist[i][k] + dist[k][j];

        if (candidate < dist[i][j]) {
          dist[i][j] = candidate;
        }
      }
    }
  }

  return dist;
}

Worst-case همچنان:

Code

O(V³)

است.

TypeScript Version

TypeScript

type DistanceMatrix = number[][];

function floydWarshall(
  matrix: DistanceMatrix
): DistanceMatrix {
  const dist = matrix.map(
    row => [...row]
  );

  const n = dist.length;

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (dist[i][k] === Infinity) {
        continue;
      }

      for (let j = 0; j < n; j++) {
        if (dist[k][j] === Infinity) {
          continue;
        }

        const candidate =
          dist[i][k] + dist[k][j];

        if (candidate < dist[i][j]) {
          dist[i][j] = candidate;
        }
      }
    }
  }

  return dist;
}

TypeScript با Path Reconstruction

TypeScript

type FloydWarshallResult = {
  dist: number[][];
  next: Array<Array<number | null>>;
};

function floydWarshallWithPath(
  matrix: number[][]
): FloydWarshallResult {
  const n = matrix.length;

  const dist = matrix.map(
    row => [...row]
  );

  const next:
    Array<Array<number | null>> =
      Array.from(
        { length: n },
        () => Array(n).fill(null)
      );

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (
        i !== j &&
        dist[i][j] !== Infinity
      ) {
        next[i][j] = j;
      }
    }
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        const candidate =
          dist[i][k] + dist[k][j];

        if (candidate < dist[i][j]) {
          dist[i][j] = candidate;
          next[i][j] = next[i][k];
        }
      }
    }
  }

  return {
    dist,
    next
  };
}

Edge Case: Empty Matrix

برای:

JSON

[]

نتیجه:

JSON

[]

است.

Edge Case: One Vertex

Matrix:

JSON

[0]

بدون Negative Self-loop همان باقی می‌ماند.

Edge Case: Negative Self-loop

اگر:

Code

dist[i][i] < 0

از ابتدا یا بعد از Relaxation باشد، Negative Cycle داریم.

Edge Case: Duplicate Edge

اگر چند Edge مستقیم بین دو Vertex وجود دارد، در Matrix اولیه باید کمترین Weight را نگه داریم.

مثلاً:

Code

A → B = 7
A → B = 3

باید:

Code

dist[A][B] = 3

باشد.

ساخت Matrix از Edge List

JavaScript

function buildMatrix(n, edges) {
  const dist = Array.from(
    { length: n },
    () => Array(n).fill(Infinity)
  );

  for (let i = 0; i < n; i++) {
    dist[i][i] = 0;
  }

  for (const [u, v, w] of edges) {
    dist[u][v] = Math.min(
      dist[u][v],
      w
    );
  }

  return dist;
}

برای Undirected Graph:

JavaScript

dist[u][v] = Math.min(dist[u][v], w);
dist[v][u] = Math.min(dist[v][u], w);

خطاهای رایج

1. اشتباه در Initialization

قطر اصلی باید:

Code

باشد.

Nodeهای بدون Edge باید:

Code

Infinity

باشند.

2. اشتباه در ترتیب Loopها

k باید نقش Intermediate Stage را داشته باشد.

3. فراموش کردن Negative Cycle Check

اگر Weight منفی داریم، بررسی:

Code

dist[i][i] < 0

مهم است.

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

O(V³) خیلی سریع رشد می‌کند.

5. استفاده برای Single Source

اگر فقط از یک Source می‌خواهید، ممکن است Dijkstra یا Bellman-Ford بسیار مناسب‌تر باشد.

6. فراموش کردن Path Matrix

اگر خود Route لازم است، فقط Distance Matrix کافی نیست.

7. استفاده از 0 به جای Infinity برای No Edge

این باعث می‌شود الگوریتم تصور کند Edge با Weight صفر وجود دارد.

چه زمانی Floyd-Warshall استفاده کنیم؟

وقتی:

All-Pairs Shortest Paths می‌خواهیم.
V کوچک یا متوسط است.
Graph Dense است.
Matrix Representation مناسب است.
Negative Edge داریم.
Reachability Matrix می‌خواهیم.
Queryهای Distance بسیار زیاد هستند.
می‌خواهیم یک Precomputation انجام دهیم.

چه زمانی مناسب نیست؟

اگر Graph بزرگ و Sparse است:

Code

Repeated Dijkstra
Johnson

ممکن است بهتر باشند.

اگر فقط Single Source می‌خواهیم:

Code

Dijkstra
Bellman-Ford
BFS

بسته به Weightها مناسب‌ترند.

اگر Graph DAG است:

Code

Topological DP

برای بعضی Shortest Pathها سریع‌تر است.

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

مسئله	الگوریتم
Unweighted Single Source	BFS
Non-negative Single Source	Dijkstra
Negative Edge Single Source	Bellman-Ford
All-Pairs با V متوسط	Floyd-Warshall
All-Pairs Sparse + Negative Edge	Johnson
DAG Shortest Path	Topological DP
Reachability All-Pairs	Warshall / Transitive Closure

جمع‌بندی

Floyd-Warshall یک الگوریتم Dynamic Programming برای:

Code

All-Pairs Shortest Paths

است.

Transition اصلی:

Code

dist[i][j]
=
min(
  dist[i][j],
  dist[i][k] + dist[k][j]
)

و ترتیب اصلی Loopها:

Code

for k
  for i
    for j

است.

Complexity:

Code

Time = O(V³)
Space = O(V²)

الگوریتم:

Directed و Undirected Graph را پشتیبانی می‌کند.
Negative Edge را پشتیبانی می‌کند.
با:
Code
1
```
dist[i][i] < 0
```
می‌تواند Negative Cycle را تشخیص دهد.
با next Matrix می‌تواند Path واقعی را بازسازی کند.
با جایگزینی min/+ با OR/AND به Transitive Closure تبدیل می‌شود.

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

Code

آیا Distance بین همه جفت Nodeها را می‌خواهم؟
تعداد Vertexها آن‌قدر نیست که O(V³) غیرعملی شود؟
آیا Matrix خروجی برای Queryهای زیاد مفید است؟

→ Floyd-Warshall

اگر فقط یک Source دارید یا Graph بسیار بزرگ و Sparse است، معمولاً الگوریتم‌های دیگری انتخاب بهتری هستند.

Floyd-Warshall یکی از مهم‌ترین الگوریتم‌های کلاسیک برای حل مسئله‌ی All-Pairs Shortest Paths است.

یعنی به‌جای اینکه فقط از یک Source به بقیه‌ی Nodeها Shortest Path پیدا کنیم، می‌خواهیم بدانیم:

Code

Shortest Path بین هر i و هر j چقدر است؟

این الگوریتم بر پایه‌ی Dynamic Programming ساخته شده و ایده‌ی آن بسیار ساده اما قدرتمند است:

برای هر Vertex واسطه‌ی k بررسی کن آیا رفتن از i به j از طریق k بهتر از مسیر فعلی است یا نه.

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

فرض کنید Graph زیر را داریم:

Code

A --3--> B
A --10-> C
B --4--> C

مسیر مستقیم:

Code

A → C
cost = 10

اما مسیر:

Code

A → B → C
cost = 3 + 4 = 7

بهتر است.

پس:

Code

dist[A][C] = 7

Floyd-Warshall این کار را برای تمام جفت رأس‌ها انجام می‌دهد.

Single-Source vs All-Pairs

Single-Source Shortest Path

مثلاً:

Code

A → همه Nodeها

الگوریتم‌های رایج:

BFS
Dijkstra
Bellman-Ford

All-Pairs Shortest Path

مثلاً:

Code

A → همه
B → همه
C → همه
...

Floyd-Warshall مستقیماً این Matrix را محاسبه می‌کند.

ایده‌ی اصلی به ساده‌ترین شکل

فرض کنید می‌خواهیم Shortest Path بین i و j را پیدا کنیم.

برای یک Vertex واسطه‌ی k دو انتخاب داریم:

Code

1. مسیر فعلی i → j
2. مسیر i → k → j

پس:

Code

dist[i][j]
=
min(
  dist[i][j],
  dist[i][k] + dist[k][j]
)

این همان قلب Floyd-Warshall است.

چرا این Dynamic Programming است؟

فرض کنید:

Code

D_k[i][j]

یعنی کوتاه‌ترین مسیر از i به j با این محدودیت که فقط Vertexهای:

Code

0 ... k

اجازه دارند به‌عنوان Intermediate Vertex استفاده شوند.

برای Vertex جدید k:

Code

D_k[i][j]
=
min(
  D_{k-1}[i][j],
  D_{k-1}[i][k] + D_{k-1}[k][j]
)

یعنی:

یا مسیر بهینه از k عبور نمی‌کند،
یا از k عبور می‌کند.

این یک recurrence کلاسیک Dynamic Programming است.

Matrix اولیه

فرض کنید Nodeها:

Code

A, B, C

باشند.

Graph:

Code

A → B = 3
B → C = 4
A → C = 10

Matrix اولیه:

Code

      A    B    C
A     0    3   10
B     ∞    0    4
C     ∞    ∞    0

چرا قطر اصلی صفر است؟

Distance هر Node به خودش بدون حرکت:

Code

است.

پس:

Code

dist[i][i] = 0

البته اگر Negative Cycle وجود داشته باشد، بعداً ممکن است:

Code

dist[i][i] < 0

شود.

این نکته برای Negative Cycle Detection بسیار مهم است.

چرا Infinity استفاده می‌کنیم؟

اگر Edge مستقیمی از i به j وجود نداشته باشد:

Code

dist[i][j] = Infinity

یعنی هنوز هیچ Path شناخته‌شده‌ای نداریم.

الگوریتم اصلی

JavaScript

function floydWarshall(matrix) {
  const dist = matrix.map(row => [...row]);
  const n = dist.length;

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        dist[i][j] = Math.min(
          dist[i][j],
          dist[i][k] + dist[k][j]
        );
      }
    }
  }

  return dist;
}

چرا k باید حلقه بیرونی باشد؟

این یکی از مهم‌ترین نکات Floyd-Warshall است.

Code

نماینده‌ی مجموعه‌ی Intermediate Vertexهایی است که تا این مرحله اجازه‌ی استفاده از آن‌ها را داده‌ایم.

پس باید ابتدا یک k را ثابت کنیم و سپس تمام i, jها را با اجازه‌ی استفاده از آن Update کنیم.

ترتیب:

Code

for k
  for i
    for j

مفهوم DP را حفظ می‌کند.

اگر Loopها را بی‌دقت جابه‌جا کنیم، ممکن است Stateهایی را در زمانی استفاده کنیم که هنوز طبق تعریف DP مجاز نیستند.

مثال مرحله‌به‌مرحله

Matrix اولیه:

Code

      A    B    C
A     0    3   10
B     ∞    0    4
C     ∞    ∞    0

وقتی:

Code

k = B

مسیر A تا C از طریق B بررسی می‌شود:

Code

dist[A][B] + dist[B][C]
=
3 + 4
=
7

چون:

Code

7 < 10

پس:

Code

dist[A][C] = 7

Matrix نهایی:

Code

      A    B    C
A     0    3    7
B     ∞    0    4
C     ∞    ∞    0

Floyd-Warshall روی Graph جهت‌دار

الگوریتم برای Directed Graph کاملاً طبیعی است.

Matrix لزوماً symmetric نیست.

مثلاً:

Code

dist[A][B] = 3

ولی ممکن است:

Code

dist[B][A] = Infinity

باشد.

Floyd-Warshall روی Graph بدون‌جهت

برای Undirected Graph، Edge:

Code

A -- B = 5

در Matrix:

Code

dist[A][B] = 5
dist[B][A] = 5

ثبت می‌شود.

آیا Negative Edge پشتیبانی می‌شود؟

بله.

Floyd-Warshall می‌تواند Edgeهای با Weight منفی داشته باشد، به شرط اینکه Shortest Path موردنظر تحت تأثیر Negative Cycle نباشد.

مثلاً:

Code

A → B = 4
B → C = -2
A → C = 10

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

Negative Cycle چیست؟

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

مثلاً:

Code

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

مجموع:

Code

2 - 5 + 1 = -2

پس Negative Cycle داریم.

چرا Negative Cycle Shortest Path را خراب می‌کند؟

اگر یک بار Cycle را طی کنیم:

Code

cost = -2

دو بار:

Code

-4

و همین‌طور:

Code

-∞

پس برای Vertexهایی که می‌توانند وارد این Cycle شوند و از آن به مقصد برسند، Shortest Path محدود و مشخصی نداریم.

تشخیص Negative Cycle با Floyd-Warshall

بعد از پایان الگوریتم، قطر اصلی Matrix را بررسی می‌کنیم.

اگر برای Vertexای:

Code

dist[i][i] < 0

باشد، Negative Cycle وجود دارد.

چرا؟

چون مسیر از i به خودش با Cost منفی پیدا شده است.

JavaScript Negative Cycle Detection

JavaScript

function hasNegativeCycle(dist) {
  for (let i = 0; i < dist.length; i++) {
    if (dist[i][i] < 0) {
      return true;
    }
  }

  return false;
}

نکته مهم درباره‌ی Negative Cycle

وجود Negative Cycle در Graph به این معنی نیست که تمام Pairها جواب نامعتبر دارند.

فقط Pairهایی که:

می‌توانند به Negative Cycle برسند،
و از آن Cycle به Destination برسند،

تحت تأثیر قرار می‌گیرند.

علامت‌گذاری Pairهای تحت تأثیر Negative Cycle

اگر:

Code

dist[i][k] !== Infinity
dist[k][k] < 0
dist[k][j] !== Infinity

باشد، Path از i به j می‌تواند از Negative Cycle عبور کند.

در این حالت می‌توان Distance را مفهومی به:

Code

-Infinity

تبدیل کرد.

نمونه

JavaScript

function markNegativeInfinity(dist) {
  const n = dist.length;

  for (let k = 0; k < n; k++) {
    if (dist[k][k] >= 0) continue;

    for (let i = 0; i < n; i++) {
      if (dist[i][k] === Infinity) continue;

      for (let j = 0; j < n; j++) {
        if (dist[k][j] === Infinity) continue;

        dist[i][j] = -Infinity;
      }
    }
  }

  return dist;
}

Path Reconstruction

گاهی Matrix فاصله کافی نیست.

می‌خواهیم بدانیم:

Code

A → B → D → F

مسیر واقعی چیست.

برای این کار یک Matrix دیگر نگه می‌داریم:

Code

next[i][j]

next Matrix چیست؟

اگر Edge مستقیم i → j وجود دارد:

Code

next[i][j] = j

وقتی Path بهتر از طریق k پیدا شود:

Code

next[i][j] = next[i][k]

یعنی اولین Step از i به سمت j همان اولین Step در مسیر i به k است.

Floyd-Warshall با Path Reconstruction

JavaScript

function floydWarshallWithPath(matrix) {
  const n = matrix.length;

  const dist = matrix.map(row => [...row]);

  const next = Array.from(
    { length: n },
    () => Array(n).fill(null)
  );

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (
        i !== j &&
        dist[i][j] !== Infinity
      ) {
        next[i][j] = j;
      }
    }
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        const throughK =
          dist[i][k] + dist[k][j];

        if (throughK < dist[i][j]) {
          dist[i][j] = throughK;
          next[i][j] = next[i][k];
        }
      }
    }
  }

  return {
    dist,
    next
  };
}

بازسازی مسیر

JavaScript

function reconstructPath(
  next,
  from,
  to
) {
  if (next[from][to] === null) {
    return null;
  }

  const path = [from];

  while (from !== to) {
    from = next[from][to];

    if (from === null) {
      return null;
    }

    path.push(from);
  }

  return path;
}

مثال Path Reconstruction

اگر Indexها:

Code

0 = A
1 = B
2 = C

و:

Code

next[0][2] = 1

باشد، یعنی Shortest Path از A به C ابتدا به B می‌رود.

Floyd-Warshall و Reachability

همین ساختار الگوریتم را می‌توان برای Reachability استفاده کرد.

به‌جای Distance از Boolean استفاده می‌کنیم.

قانون:

Code

reachable[i][j]
=
reachable[i][j]
OR
(
  reachable[i][k]
  AND
  reachable[k][j]
)

Transitive Closure

خروجی Boolean All-Pairs Reachability را معمولاً:

Code

Transitive Closure

می‌نامند.

Warshall Algorithm

نسخه Boolean الگوریتم معمولاً به نام:

Code

Warshall's Algorithm

شناخته می‌شود.

JavaScript برای Reachability

JavaScript

function transitiveClosure(matrix) {
  const reach = matrix.map(
    row => [...row]
  );

  const n = reach.length;

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        reach[i][j] =
          reach[i][j] ||
          (
            reach[i][k] &&
            reach[k][j]
          );
      }
    }
  }

  return reach;
}

کاربرد Reachability Matrix

مثلاً:

Dependency analysis
Permission propagation
Course prerequisite closure
Service reachability
Workflow reachability
Network connectivity queries

Floyd-Warshall vs Dijkstra

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

Floyd-Warshall

Code

All-Pairs
O(V³)

Dijkstra

یک بار:

Code

Single Source

اگر از هر Vertex اجرا شود:

Code

V × Dijkstra

Complexity با Heap تقریباً:

Code

O(V(E + V) log V)

در Sparse Graph ممکن است بهتر از Floyd-Warshall باشد.

چه زمانی Floyd-Warshall بهتر است؟

وقتی:

V نسبتاً کوچک یا متوسط است.
Graph Dense است.
All-Pairs Query زیاد داریم.
Matrix Representation طبیعی است.
Negative Edge داریم ولی Negative Cycle مؤثر نداریم.
سادگی Implementation مهم است.

چه زمانی Dijkstraهای تکراری بهترند؟

وقتی:

Graph Sparse است.
Weightها Non-negative هستند.
V بزرگ‌تر است.
فقط از تعدادی Source محدود Query داریم.

Floyd-Warshall vs Bellman-Ford

Bellman-Ford

Code

Single Source
O(VE)

پشتیبانی:

Negative Edge
Negative Cycle Detection

Floyd-Warshall

Code

All Pairs
O(V³)

پشتیبانی:

Negative Edge
Negative Cycle Detection از diagonal

Floyd-Warshall vs Johnson

Johnson برای:

Code

All-Pairs Shortest Path

روی Graph Sparse مناسب است.

روش:

Bellman-Ford
Reweight
Dijkstra از هر Vertex

برای Graph Sparse بزرگ، Johnson ممکن است بهتر از Floyd-Warshall باشد.

Floyd-Warshall vs BFS

اگر Graph Unweighted باشد و All-Pairs Distance بخواهیم، می‌توانیم BFS را از هر Vertex اجرا کنیم.

در Sparse Graph:

Code

O(V(V + E))

ممکن است بهتر از:

Code

O(V³)

باشد.

چرا Floyd-Warshall برای Graph Dense مناسب است؟

در Dense Graph:

Code

E ≈ V²

روش‌های مبتنی بر Edge هم به Complexity بالا نزدیک می‌شوند.

در چنین شرایطی Matrix و O(V³) می‌تواند انتخاب ساده و منطقی باشد.

کاربرد: Routing Matrix

فرض کنید یک Network کوچک یا متوسط داریم و می‌خواهیم بین تمام Nodeها Shortest Cost را Precompute کنیم.

Matrix نهایی:

Code

dist[i][j]

می‌تواند مستقیماً برای Queryهای بعدی استفاده شود.

کاربرد: Logistics

اگر تعداد Hubها محدود باشد:

Code

Hub 1
Hub 2
Hub 3
...

می‌توان Distance Matrix کامل را Precompute کرد.

بعد Query:

Code

cost(A, B)

در:

Code

O(1)

پاسخ داده می‌شود.

کاربرد: شعب و انبارها

اگر شرکت چند ده یا چند صد Branch/Depot داشته باشد، ممکن است All-Pairs Distance Matrix برای Planning مفید باشد.

البته در سیستم واقعی Road Network بسیار بزرگ، معمولاً الگوریتم‌های تخصصی‌تر استفاده می‌شوند.

کاربرد: Dependency Graph

اگر Edge Weight معنای Cost داشته باشد، می‌توان Cost بین همه Moduleها یا Stateها را محاسبه کرد.

اگر فقط Reachability مهم باشد، Transitive Closure مناسب‌تر است.

کاربرد: Game Map کوچک

در Game با تعداد State/Region محدود، می‌توان همه فاصله‌ها را Precompute کرد.

بعد AI می‌تواند Queryهای Distance را بسیار سریع جواب دهد.

کاربرد: Network Latency Matrix

اگر Nodeها محدود باشند و Edge Weight = latency باشد، Floyd-Warshall می‌تواند کمترین Latency نظری بین همه Pairها را محاسبه کند.

Dynamic Programming View

State اصلی:

Code

dist[i][j]

و Transition:

Code

dist[i][j]
=
min(
  dist[i][j],
  dist[i][k] + dist[k][j]
)

این یکی از شفاف‌ترین مثال‌های DP روی Graph است.

In-Place DP چرا کار می‌کند؟

به‌جای ساختن Matrix جدا برای هر k، همان Matrix را Update می‌کنیم.

این کار درست است چون در مرحله‌ی k فقط اطلاعاتی استفاده می‌کنیم که Intermediate Vertexهای مجازشان حداکثر k هستند.

این باعث کاهش Memory از:

Code

O(V³)

به:

Code

O(V²)

می‌شود.

Complexity زمانی

سه Loop داریم:

Code

k
i
j

هرکدام تا V.

پس:

Code

Time = O(V³)

Complexity فضایی

Matrix فاصله:

Code

V × V

است.

پس:

Code

Space = O(V²)

اگر Path Reconstruction هم بخواهیم:

Code

next matrix = O(V²)

و همچنان Big-O:

Code

O(V²)

می‌ماند.

آیا می‌توان Space را کمتر کرد؟

برای خروجی کامل All-Pairs Distance خودمان به Matrix:

Code

O(V²)

نیاز داریم.

پس کاهش چشمگیر Space معمولاً ممکن نیست اگر تمام جواب‌ها را همزمان بخواهیم.

Infinity Handling

در JavaScript:

Code

Infinity + number = Infinity

است.

اما برای خوانایی و کنترل بهتر می‌توان قبل از Transition بررسی کرد:

JavaScript

if (
  dist[i][k] === Infinity ||
  dist[k][j] === Infinity
) {
  continue;
}

نسخه Optimized‌تر از نظر محاسبات بی‌فایده

JavaScript

function floydWarshall(matrix) {
  const dist = matrix.map(
    row => [...row]
  );

  const n = dist.length;

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (dist[i][k] === Infinity) {
        continue;
      }

      for (let j = 0; j < n; j++) {
        if (dist[k][j] === Infinity) {
          continue;
        }

        const candidate =
          dist[i][k] + dist[k][j];

        if (candidate < dist[i][j]) {
          dist[i][j] = candidate;
        }
      }
    }
  }

  return dist;
}

Worst-case همچنان:

Code

O(V³)

است.

TypeScript Version

TypeScript

type DistanceMatrix = number[][];

function floydWarshall(
  matrix: DistanceMatrix
): DistanceMatrix {
  const dist = matrix.map(
    row => [...row]
  );

  const n = dist.length;

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (dist[i][k] === Infinity) {
        continue;
      }

      for (let j = 0; j < n; j++) {
        if (dist[k][j] === Infinity) {
          continue;
        }

        const candidate =
          dist[i][k] + dist[k][j];

        if (candidate < dist[i][j]) {
          dist[i][j] = candidate;
        }
      }
    }
  }

  return dist;
}

TypeScript با Path Reconstruction

TypeScript

type FloydWarshallResult = {
  dist: number[][];
  next: Array<Array<number | null>>;
};

function floydWarshallWithPath(
  matrix: number[][]
): FloydWarshallResult {
  const n = matrix.length;

  const dist = matrix.map(
    row => [...row]
  );

  const next:
    Array<Array<number | null>> =
      Array.from(
        { length: n },
        () => Array(n).fill(null)
      );

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (
        i !== j &&
        dist[i][j] !== Infinity
      ) {
        next[i][j] = j;
      }
    }
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        const candidate =
          dist[i][k] + dist[k][j];

        if (candidate < dist[i][j]) {
          dist[i][j] = candidate;
          next[i][j] = next[i][k];
        }
      }
    }
  }

  return {
    dist,
    next
  };
}

Edge Case: Empty Matrix

برای:

JSON

[]

نتیجه:

JSON

[]

است.

Edge Case: One Vertex

Matrix:

JSON

[0]

بدون Negative Self-loop همان باقی می‌ماند.

Edge Case: Negative Self-loop

اگر:

Code

dist[i][i] < 0

از ابتدا یا بعد از Relaxation باشد، Negative Cycle داریم.

Edge Case: Duplicate Edge

اگر چند Edge مستقیم بین دو Vertex وجود دارد، در Matrix اولیه باید کمترین Weight را نگه داریم.

مثلاً:

Code

A → B = 7
A → B = 3

باید:

Code

dist[A][B] = 3

باشد.

ساخت Matrix از Edge List

JavaScript

function buildMatrix(n, edges) {
  const dist = Array.from(
    { length: n },
    () => Array(n).fill(Infinity)
  );

  for (let i = 0; i < n; i++) {
    dist[i][i] = 0;
  }

  for (const [u, v, w] of edges) {
    dist[u][v] = Math.min(
      dist[u][v],
      w
    );
  }

  return dist;
}

برای Undirected Graph:

JavaScript

dist[u][v] = Math.min(dist[u][v], w);
dist[v][u] = Math.min(dist[v][u], w);

خطاهای رایج

1. اشتباه در Initialization

قطر اصلی باید:

Code

باشد.

Nodeهای بدون Edge باید:

Code

Infinity

باشند.

2. اشتباه در ترتیب Loopها

k باید نقش Intermediate Stage را داشته باشد.

3. فراموش کردن Negative Cycle Check

اگر Weight منفی داریم، بررسی:

Code

dist[i][i] < 0

مهم است.

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

O(V³) خیلی سریع رشد می‌کند.

5. استفاده برای Single Source

اگر فقط از یک Source می‌خواهید، ممکن است Dijkstra یا Bellman-Ford بسیار مناسب‌تر باشد.

6. فراموش کردن Path Matrix

اگر خود Route لازم است، فقط Distance Matrix کافی نیست.

7. استفاده از 0 به جای Infinity برای No Edge

این باعث می‌شود الگوریتم تصور کند Edge با Weight صفر وجود دارد.

چه زمانی Floyd-Warshall استفاده کنیم؟

وقتی:

All-Pairs Shortest Paths می‌خواهیم.
V کوچک یا متوسط است.
Graph Dense است.
Matrix Representation مناسب است.
Negative Edge داریم.
Reachability Matrix می‌خواهیم.
Queryهای Distance بسیار زیاد هستند.
می‌خواهیم یک Precomputation انجام دهیم.

چه زمانی مناسب نیست؟

اگر Graph بزرگ و Sparse است:

Code

Repeated Dijkstra
Johnson

ممکن است بهتر باشند.

اگر فقط Single Source می‌خواهیم:

Code

Dijkstra
Bellman-Ford
BFS

بسته به Weightها مناسب‌ترند.

اگر Graph DAG است:

Code

Topological DP

برای بعضی Shortest Pathها سریع‌تر است.

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

مسئله	الگوریتم
Unweighted Single Source	BFS
Non-negative Single Source	Dijkstra
Negative Edge Single Source	Bellman-Ford
All-Pairs با V متوسط	Floyd-Warshall
All-Pairs Sparse + Negative Edge	Johnson
DAG Shortest Path	Topological DP
Reachability All-Pairs	Warshall / Transitive Closure

جمع‌بندی

Floyd-Warshall یک الگوریتم Dynamic Programming برای:

Code

All-Pairs Shortest Paths

است.

Transition اصلی:

Code

dist[i][j]
=
min(
  dist[i][j],
  dist[i][k] + dist[k][j]
)

و ترتیب اصلی Loopها:

Code

for k
  for i
    for j

است.

Complexity:

Code

Time = O(V³)
Space = O(V²)

الگوریتم:

Directed و Undirected Graph را پشتیبانی می‌کند.
Negative Edge را پشتیبانی می‌کند.
با:
Code
1
```
dist[i][i] < 0
```
می‌تواند Negative Cycle را تشخیص دهد.
با next Matrix می‌تواند Path واقعی را بازسازی کند.
با جایگزینی min/+ با OR/AND به Transitive Closure تبدیل می‌شود.

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

Code

آیا Distance بین همه جفت Nodeها را می‌خواهم؟
تعداد Vertexها آن‌قدر نیست که O(V³) غیرعملی شود؟
آیا Matrix خروجی برای Queryهای زیاد مفید است؟

→ Floyd-Warshall

اگر فقط یک Source دارید یا Graph بسیار بزرگ و Sparse است، معمولاً الگوریتم‌های دیگری انتخاب بهتری هستند.

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

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

Single-Source vs All-Pairs

Single-Source Shortest Path

All-Pairs Shortest Path

ایده‌ی اصلی به ساده‌ترین شکل

چرا این Dynamic Programming است؟

Matrix اولیه

چرا قطر اصلی صفر است؟

چرا Infinity استفاده می‌کنیم؟

الگوریتم اصلی

چرا k باید حلقه بیرونی باشد؟

مثال مرحله‌به‌مرحله

Floyd-Warshall روی Graph جهت‌دار

Floyd-Warshall روی Graph بدون‌جهت

آیا Negative Edge پشتیبانی می‌شود؟

Negative Cycle چیست؟

چرا Negative Cycle Shortest Path را خراب می‌کند؟

تشخیص Negative Cycle با Floyd-Warshall

JavaScript Negative Cycle Detection

نکته مهم درباره‌ی Negative Cycle

علامت‌گذاری Pairهای تحت تأثیر Negative Cycle

نمونه

Path Reconstruction

next Matrix چیست؟

Floyd-Warshall با Path Reconstruction

بازسازی مسیر

مثال Path Reconstruction

Floyd-Warshall و Reachability

Transitive Closure

Warshall Algorithm

JavaScript برای Reachability

کاربرد Reachability Matrix

Floyd-Warshall vs Dijkstra

Floyd-Warshall

Dijkstra

چه زمانی Floyd-Warshall بهتر است؟

چه زمانی Dijkstraهای تکراری بهترند؟

Floyd-Warshall vs Bellman-Ford

Bellman-Ford

Floyd-Warshall

Floyd-Warshall vs Johnson

Floyd-Warshall vs BFS

چرا Floyd-Warshall برای Graph Dense مناسب است؟

کاربرد: Routing Matrix

کاربرد: Logistics

کاربرد: شعب و انبارها

کاربرد: Dependency Graph

کاربرد: Game Map کوچک

کاربرد: Network Latency Matrix

Dynamic Programming View

In-Place DP چرا کار می‌کند؟

Complexity زمانی

Complexity فضایی

آیا می‌توان Space را کمتر کرد؟

Infinity Handling

نسخه Optimized‌تر از نظر محاسبات بی‌فایده

TypeScript Version

TypeScript با Path Reconstruction

Edge Case: Empty Matrix

Edge Case: One Vertex

Edge Case: Negative Self-loop

Edge Case: Duplicate Edge

ساخت Matrix از Edge List

خطاهای رایج

1. اشتباه در Initialization

2. اشتباه در ترتیب Loopها

3. فراموش کردن Negative Cycle Check

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

5. استفاده برای Single Source

6. فراموش کردن Path Matrix

7. استفاده از 0 به جای Infinity برای No Edge

چه زمانی Floyd-Warshall استفاده کنیم؟

چه زمانی مناسب نیست؟

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

جمع‌بندی

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

الگوریتم Prim چیست؟ ساخت Minimum Spanning Tree از صفر تا صد

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

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