الگوریتم فلوید وارشال چیست، آموزش الگوریتم فلوید وارشال

الگوریتم فلوید وارشال چیست، این صفحه عالی به بررسی و آموزش الگوریتم فلوید وارشال با مثال پرداخته و نحوه پیاده سازی الگوریتم فلوید وارشال و پیچیدگی آن را گفته

الگوریتم فلوید-وارشال الگوریتمی برای یافتن کوتاه‌ترین مسیر بین تمام جفت رئوس در یک گرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریف Graph در این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ... وزن‌دار است. این الگوریتم برای گراف‌های وزن دار جهت‌دار و بدون جهت کار می‌کند، اما برای گراف‌هایی با دور منفی (که مجموع یال‌های یک دور، منفی است) کار نمی‌کند. در این آموزش نحوه عملکرد الگوریتم فلوید-وارشال را خواهید آموخت؛ همچنین نمونه‌های پیاده‌سازی از الگوریتم فلوید-وارشال را در پایتون، جاوا، C و سی پلاس پلاس خواهید دید.

نحوه کارکرد الگوریتم فلوید وارشال با مثال

در ادامه الگوریتم فلوید وارشال را با ارائه یک مثال بررسی می‌کنیم. گراف زیر را در نظر بگیرید:

نمونه ای از یک گراف که الگوریتم فلوید وارشال روی آن پیاده سازی می شود

یک ماتریس${\mathrm{A}}_0$ با بعد $\mathrm{n*n}$ ایجاد کنید که n تعداد رئوس گراف است. سطر و ستون به ترتیب به صورت i و j نمایش داده می‌شوند. i و j رئوس گراف هستند. هر خانه ${\mathrm{A}}_{\left[\mathrm{i}\right]\left[\mathrm{j}\right]}$ با فاصله رأس i تا رأس j پر شده است. اگر مسیری از رأس i ام به رأس j ام وجود نداشته باشد، مقادر اندیس بی‌نهایت باقی می‌ماند.

${\mathrm{A}}_0\mathrm{=}\left[\mathrm{0\ \ 3\ \ }\mathrm{\infty }\mathrm{\ \ 5\ \ 2\ \ 0\ \ }\mathrm{\infty }\mathrm{\ \ 4\ \ }\mathrm{\infty }\mathrm{\ \ 1\ \ 0\ \ }\mathrm{\infty }\mathrm{\ \ }\mathrm{\infty }\mathrm{\ \ }\mathrm{\infty }\mathrm{\ \ 2\ \ 0}\right]$

حال با استفاده از ماتریس ${\mathrm{A}}_0$ یک ماتریس ${\mathrm{A}}_1$ ایجاد کنید. عناصر ستون اول و سطر اول به همان صورت باقی می‌مانند. اندیس‌های باقی‌مانده به روش زیر پر می‌شوند.

فرض کنید k رأس میانی در کوتاه‌ترین مسیر از مبدأ تا مقصد باشد. در این مرحله k اولین راس است. ${\mathrm{A}}_{\left[\mathrm{i}\right]\left[\mathrm{j}\right]}$ با $\left({\mathrm{A}}_{\left[\mathrm{i}\right]\left[\mathrm{k}\right]}\mathrm{+}{\mathrm{A}}_{\left[\mathrm{k}\right]\left[\mathrm{j}\right]}\right)$ پر می‌شود اگر $\left({\mathrm{A}}_{\left[\mathrm{i}\right]\left[\mathrm{j}\right]}\mathrm{>}{\mathrm{A}}_{\left[\mathrm{i}\right]\left[\mathrm{k}\right]}\mathrm{+}{\mathrm{A}}_{\left[\mathrm{k}\right]\left[\mathrm{j}\right]}\right)$. یعنی اگر فاصله مستقیم از مبدأ تا مقصد بیشتر از مسیر عبور از رأس k باشد، آنگاه اندیس با مقدار ${\mathrm{A}}_{\left[\mathrm{i}\right]\left[\mathrm{k}\right]}\mathrm{+}{\mathrm{A}}_{\left[\mathrm{k}\right]\left[\mathrm{j}\right]}$ پر می‌شود. در این مرحله k رأس 1 است. فاصله رأس مبدأ تا رأس مقصد را از طریق راس k محاسبه می‌کنیم.

${\mathrm{A}}_{\mathrm{1}}\mathrm{=}\left[\mathrm{0\ \ 3\ \ }\mathrm{\infty }\mathrm{\ \ 5\ \ 2\ \ 0\ \ 9\ \ 4\ \ }\mathrm{\infty }\mathrm{\ \ 1\ \ 0\ \ 8\ \ }\mathrm{\infty }\mathrm{\ \ }\mathrm{\infty }\mathrm{\ \ 2\ \ 0}\right]\mathrm{\ \ \ \ \ \ \ \ }\mathrm{\Rightarrow }\mathrm{\ \ \ \ \ \ \ \ }{\mathrm{A}}_{\mathrm{1}}\mathrm{=}\left[\mathrm{0\ \ 3\ \ }\mathrm{\infty }\mathrm{\ \ 5\ \ 2\ \ 0\ \ 0\ \ 0}\right]$

به عنوان مثال: برای ${\mathrm{A}}_{\mathrm{1}}\mathrm{=}\left[\mathrm{2,}\mathrm{\ }\mathrm{4}\right]$، فاصله مستقیم از رأس 2 تا 4 برابر 4 است و مجموع فاصله از رأس 2 تا 4 از طریق رأس (یعنی از رأس 2 به 1 و از رأس 1 تا 4) برابر است با 7. از آن‌جایی که $7>4$، ${\mathrm{A}}_{\mathrm{1}}\mathrm{=}\left[\mathrm{2,}\mathrm{\ }\mathrm{4}\right]$ با 4 پر می‌شود. به طور مشابه، ${\mathrm{A}}_2$ با استفاده از ${\mathrm{A}}_1$ ایجاد می‌شود. عناصر ستون دوم و سطر دوم به همان صورت باقی می‌مانند. در این مرحله k رأس دوم (یعنی رأس 2) است. مراحل باقی‌مانده مانند مرحله 2 است.

${\mathrm{A}}_{\mathrm{2}}\mathrm{=}\left[\mathrm{0\ \ 3\ \ 9\ \ 5\ \ 2\ \ 0\ \ 9\ \ 4\ \ 3\ \ 1\ \ 0\ \ 5\ \ }\mathrm{\infty }\mathrm{\ \ }\mathrm{\infty }\mathrm{\ \ 2\ \ 0}\right]\mathrm{\ \ \ \ \ \ \ \ }\mathrm{\Rightarrow }\mathrm{\ \ \ \ \ \ \ \ }{\mathrm{A}}_{\mathrm{2}}\mathrm{=}\left[0\mathrm{\ \ 3\ \ 2\ \ 0\ \ 9\ \ 4\ \ 1\ \ 0\ \ }\mathrm{\infty }\mathrm{\ \ 0}\right]$

بطور مشابه ${\mathrm{A}}_3$ و ${\mathrm{A}}_4$ را هم می‌سازیم:

${\mathrm{A}}_{\mathrm{3}}\mathrm{=}\left[\mathrm{0\ \ 3\ \ 9\ \ 5\ \ 2\ \ 0\ \ 9\ \ 4\ \ 3\ \ 1\ \ 0\ \ 5\ \ 5\ \ 3\ \ 2\ \ 0}\right]\mathrm{\ \ \ \ \ \ \ \ }\mathrm{\Rightarrow }\mathrm{\ \ \ \ \ \ \ \ }{\mathrm{A}}_{\mathrm{3}}\mathrm{=}\left[\mathrm{0\ \ }\mathrm{\infty }\mathrm{\ \ 0\ \ 9\ \ }\mathrm{\infty }\mathrm{\ \ 1\ \ 0\ \ 8\ \ 2\ \ 0}\right]$

${\mathrm{A}}_{\mathrm{4}}\mathrm{=}\left[\mathrm{0\ \ 3\ \ 7\ \ 5\ \ 2\ \ 0\ \ 6\ \ 4\ \ 3\ \ 1\ \ 0\ \ 5\ \ 5\ \ 3\ \ 2\ \ 0}\right]\mathrm{\ \ \ \ \ \ \ \ }\mathrm{\Rightarrow }\mathrm{\ \ \ \ \ \ \ \ }{\mathrm{A}}_{\mathrm{4}}\mathrm{=}\left[\mathrm{0\ \ 5\ \ 0\ \ 4\ \ 0\ \ 5\ \ 5\ \ 3\ \ 2\ \ 0}\right]$

${\mathrm{A}}_4$ کوتاه‌ترین مسیر را بین هر جفت رئوس نشان می‌دهد.

حتما بخوانید :

الگوریتم SVM چیست ⚡️ SVM یا Support vector machines چیست

پیاده سازی الگوریتم فلوید وارشال

حال که با نحوه کارکرد الگوریتم فلوید-وارشال آشنا شدیم، ابتدا شبه کد آن و سپس پیاده‌سازی این الگوریتم با زبان های برنامه نویسی مختلف را خواهیم دید.

Pseudo Code

n = no of vertices
A = matrix of dimension n*n
for k = 1 to n
  for i = 1 to n
    for j = 1 to n
      Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])
return A

n = no of vertices
A = matrix of dimension n*n
for k = 1 to n
  for i = 1 to n
    for j = 1 to n
      Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])
return A

Python

# Floyd Warshall Algorithm in python


# The number of vertices
nV = 4

INF = 999


# Algorithm implementation
def floyd_warshall(G):
  distance = list(map(lambda i: list(map(lambda j: j, i)), G))

  # Adding vertices individually
  for k in range(nV):
    for i in range(nV):
      for j in range(nV):
        distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
  print_solution(distance)


# Printing the solution
def print_solution(distance):
  for i in range(nV):
    for j in range(nV):
	  if(distance[i][j] == INF):
        print("INF", end=" ")
      else:
        print(distance[i][j], end="  ")
      print(" ")


G = [[0, 3, INF, 5],
     [2, 0, INF, 4],
     [INF, 1, 0, INF],
     [INF, INF, 2, 0]]
floyd_warshall(G)

# Floyd Warshall Algorithm in python


# The number of vertices
nV = 4

INF = 999


# Algorithm implementation
def floyd_warshall(G):
  distance = list(map(lambda i: list(map(lambda j: j, i)), G))

  # Adding vertices individually
  for k in range(nV):
    for i in range(nV):
      for j in range(nV):
        distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
  print_solution(distance)


# Printing the solution
def print_solution(distance):
  for i in range(nV):
    for j in range(nV):
	  if(distance[i][j] == INF):
        print("INF", end=" ")
      else:
        print(distance[i][j], end="  ")
      print(" ")


G = [[0, 3, INF, 5],
     [2, 0, INF, 4],
     [INF, 1, 0, INF],
     [INF, INF, 2, 0]]
floyd_warshall(G)

Java

// Floyd Warshall Algorithm in Java

class FloydWarshall {
  final static int INF = 9999, nV = 4;

  // Implementing floyd warshall algorithm
  void floydWarshall(int graph[][]) {
    int matrix[][] = new int[nV][nV];
    int I, j, k;

    for (I = 0; I < nV; i++)
      for (j = 0; j < nV; j++)
        matrix[i][j] = graph[i][j];

    // Adding vertices individually
    for (k = 0; k < nV; k++) {
      for (I = 0; I < nV; i++) {
        for (j = 0; j < nV; j++) {
          if (matrix[i][k] + matrix[k][j]  matrix[i][j])
            matrix[i][j] = matrix[i][k] + matrix[k][j];
        }
      }
    }
    printMatrix(matrix);
  }

  void printMatrix(int matrix[][]) {
    for (int I = 0; I < nV; ++i) {
      for (int j = 0; j < nV; ++j) {
        if (matrix[i][j] == INF)
          System.out.print(“INF “);
        else
          System.out.print(matrix[i][j] + “  “);
      }
      System.out.println();
    }
  }

  public static void main(String[] args) {
    int graph[][] = { { 0, 3, INF, 5 }, { 2, 0, INF, 4 }, { INF, 1, 0, INF }, { INF, INF, 2, 0 } };
    FloydWarshall a = new FloydWarshall();
    a.floydWarshall(graph);
  }
}

// Floyd Warshall Algorithm in Java

class FloydWarshall {
  final static int INF = 9999, nV = 4;

  // Implementing floyd warshall algorithm
  void floydWarshall(int graph[][]) {
    int matrix[][] = new int[nV][nV];
    int I, j, k;

    for (I = 0; I < nV; i++)
      for (j = 0; j < nV; j++)
        matrix[i][j] = graph[i][j];

    // Adding vertices individually
    for (k = 0; k < nV; k++) {
      for (I = 0; I < nV; i++) {
        for (j = 0; j < nV; j++) {
          if (matrix[i][k] + matrix[k][j]  matrix[i][j])
            matrix[i][j] = matrix[i][k] + matrix[k][j];
        }
      }
    }
    printMatrix(matrix);
  }

  void printMatrix(int matrix[][]) {
    for (int I = 0; I < nV; ++i) {
      for (int j = 0; j < nV; ++j) {
        if (matrix[i][j] == INF)
          System.out.print(“INF “);
        else
          System.out.print(matrix[i][j] + “  “);
      }
      System.out.println();
    }
  }

  public static void main(String[] args) {
    int graph[][] = { { 0, 3, INF, 5 }, { 2, 0, INF, 4 }, { INF, 1, 0, INF }, { INF, INF, 2, 0 } };
    FloydWarshall a = new FloydWarshall();
    a.floydWarshall(graph);
  }
}

C

// Floyd-Warshall Algorithm in C

#include <stdio.h>

// defining the number of vertices
#define nV 4

#define INF 999

void printMatrix(int matrix[][nV]);

// Implementing floyd warshall algorithm
void floydWarshall(int graph[][nV]) {
  int matrix[nV][nV], i, j, k;

  for (i = 0; i < nV; i++)
    for (j = 0; j < nV; j++)
      matrix[i][j] = graph[i][j];

  // Adding vertices individually
  for (k = 0; k < nV; k++) {
    for (i = 0; i < nV; i++) {
      for (j = 0; j < nV; j++) {
        if (matrix[i][k] + matrix[k][j]  matrix[i][j])
          matrix[i][j] = matrix[i][k] + matrix[k][j];
      }
    }
  }
  printMatrix(matrix);
}

void printMatrix(int matrix[][nV]) {
  for (int i = 0; i < nV; i++) {
    for (int j = 0; j < nV; j++) {
      if (matrix[i][j] == INF)
        printf("%4s", "INF");
      else
        printf("%4d", matrix[i][j]);
    }
    printf("\n");
  }
}

int main() {
  int graph[nV][nV] = {{0, 3, INF, 5},
             {2, 0, INF, 4},
             {INF, 1, 0, INF},
             {INF, INF, 2, 0}};
  floydWarshall(graph);
}

// Floyd-Warshall Algorithm in C

#include <stdio.h>

// defining the number of vertices
#define nV 4

#define INF 999

void printMatrix(int matrix[][nV]);

// Implementing floyd warshall algorithm
void floydWarshall(int graph[][nV]) {
  int matrix[nV][nV], i, j, k;

  for (i = 0; i  nV; i++)
    for (j = 0; j  nV; j++)
      matrix[i][j] = graph[i][j];

  // Adding vertices individually
  for (k = 0; k  nV; k++) {
    for (i = 0; i  nV; i++) {
      for (j = 0; j  nV; j++) {
        if (matrix[i][k] + matrix[k][j]  matrix[i][j])
          matrix[i][j] = matrix[i][k] + matrix[k][j];
      }
    }
  }
  printMatrix(matrix);
}

void printMatrix(int matrix[][nV]) {
  for (int i = 0; i  nV; i++) {
    for (int j = 0; j  nV; j++) {
      if (matrix[i][j] == INF)
        printf("%4s", "INF");
      else
        printf("%4d", matrix[i][j]);
    }
    printf("\n");
  }
}

int main() {
  int graph[nV][nV] = {{0, 3, INF, 5},
             {2, 0, INF, 4},
             {INF, 1, 0, INF},
             {INF, INF, 2, 0}};
  floydWarshall(graph);
}

C++

// Floyd-Warshall Algorithm in C++

#include <iostream>
using namespace std;

// defining the number of vertices
#define nV 4

#define INF 999

void printMatrix(int matrix[][nV]);

// Implementing floyd warshall algorithm
void floydWarshall(int graph[][nV]) {
  int matrix[nV][nV], i, j, k;

  for (i = 0; i < nV; i++)
    for (j = 0; j < nV; j++)
      matrix[i][j] = graph[i][j];

  // Adding vertices individually
  for (k = 0; k < nV; k++) {
    for (i = 0; i < nV; i++) {
      for (j = 0; j < nV; j++) {
        if (matrix[i][k] + matrix[k][j]  matrix[i][j])
          matrix[i][j] = matrix[i][k] + matrix[k][j];
      }
    }
  }
  printMatrix(matrix);
}

void printMatrix(int matrix[][nV]) {
  for (int i = 0; i < nV; i++) {
    for (int j = 0; j < nV; j++) {
      if (matrix[i][j] == INF)
        printf("%4s", "INF");
      else
        printf("%4d", matrix[i][j]);
    }
    printf("\n");
  }
}

int main() {
  int graph[nV][nV] = {{0, 3, INF, 5},
             {2, 0, INF, 4},
             {INF, 1, 0, INF},
             {INF, INF, 2, 0}};
  floydWarshall(graph);
}

// Floyd-Warshall Algorithm in C++

#include <iostream>
using namespace std;

// defining the number of vertices
#define nV 4

#define INF 999

void printMatrix(int matrix[][nV]);

// Implementing floyd warshall algorithm
void floydWarshall(int graph[][nV]) {
  int matrix[nV][nV], i, j, k;

  for (i = 0; i < nV; i++)
    for (j = 0; j < nV; j++)
      matrix[i][j] = graph[i][j];

  // Adding vertices individually
  for (k = 0; k < nV; k++) {
    for (i = 0; i < nV; i++) {
      for (j = 0; j < nV; j++) {
        if (matrix[i][k] + matrix[k][j]  matrix[i][j])
          matrix[i][j] = matrix[i][k] + matrix[k][j];
      }
    }
  }
  printMatrix(matrix);
}

void printMatrix(int matrix[][nV]) {
  for (int i = 0; i < nV; i++) {
    for (int j = 0; j < nV; j++) {
      if (matrix[i][j] == INF)
        printf("%4s", "INF");
      else
        printf("%4d", matrix[i][j]);
    }
    printf("\n");
  }
}

int main() {
  int graph[nV][nV] = {{0, 3, INF, 5},
             {2, 0, INF, 4},
             {INF, 1, 0, INF},
             {INF, INF, 2, 0}};
  floydWarshall(graph);
}

پیچیدگی زمانی و فضایی الگوریتم فلوید وارشال

در این الگوریتم سه حلقه وجود دارد. هر حلقه پیچیدگی‌های ثابتی دارد بنابراین، پیچیدگی زمانی الگوریتم فلوید-وارشال $\mathrm{O}\left({\mathrm{n}}^{\mathrm{3}}\right)$ است. پیچیدگی فضایی الگوریتم فلوید-وارشال $\mathrm{O}\left({\mathrm{n}}^{\mathrm{2}}\right)$ است.

حتما بخوانید :

الگوریتم کراسکال یا کروسکال⚡️مثال+پیاده سازی+پیچیدگی زمانی

مقایسه الگوریتم فلوید وارشال و الگوریتم بلمن فورد

الگوریتم بلمن-فورد یک الگوریتم برای پیدا کردن کوتاه‌ترین مسیر از یک مبدأ است که با ریلکس کردن مکرر یال‌ها در گراف کار می‌کند، تا زمانی که کوتاه‌ترین مسیر برای همه رئوس پیدا شود. این الگوریتم به ویژه برای گراف‌هایی با یال‌های با وزن منفی کاربردی است، زیرا می تواند دورهای منفی را تشخیص دهد. در حالی که الگوریتم فلوید-وارشال یک الگوریتم برای یافتن کوتاه‌ترین مسیر از چند مبدأ است که با محاسبه کوتاه‌ترین مسیر بین تمام جفت‌های رئوس در گراف با استفاده از برنامه نویسی پویا کار می‌کند.

کاربردهای الگوریتم فلوید وارشال

الگوریتم فلوید-وارشال کاربردهای زیادی دارد که از بین آن‌ها می‌توان به موارد زیر اشاره کرد:

یافتن کوتاه‌ترین مسیر یک گراف جهت دار
یافتن بسته بودن نسبت به تعدی گراف‌های جهت دار
پیدا کردن وارون ماتریس‌ها
آزمایش دوبخشی بودن یک گراف بدون جهت

حتما بخوانید :

الگوریتم جنگل تصادفی ⚡️ الگوریتم جنگل چیست

جمع‌بندی

الگوریتم فلوید-وارشال، الگوریتمی برای مسائل کوتاه‌ترین مسیر بین تمام جفت‌های رئوس در یک گراف است. این الگوریتم از رویکرد برنامه نویسی پویا برای یافتن کوتاه‌ترین مسیر پیروی می‌کند. در این مقاله به بررسی این الگوریتم پرداختیم و مثالی برای درک بهتر این الگوریتم ارائه کردیم؛ همچنین به بررسی پیچیدگی مرتبه زمانی و فضایی این الگوریتم پرداختیم و این الگوریتم را با استفاده از زبان‌های برنامه‌نویسی مختلف پیاده‌سازی کردیم.

الگوریتم فلوید وارشال چیست؟

الگوریتم فلوید-وارشال، الگوریتمی برای یافتن کوتاه‌ترین مسیر بین تمام جفت رئوس در یک گراف وزن دار است. این الگوریتم برای گراف‌های وزن دار و بدون وزن کار می‌کند، اما کاربردی برای گراف‌های با دور منفی ندارد.

پیچیدگی زمانی و فضایی الگوریتم فلوید وارشال به چه صورت است؟

پیچیدگی زمانی الگوریتم فلوید-وارشال برابر با $\mathrm{O}\left({\mathrm{n}}^{\mathrm{3}}\right)$ می باشد. همچنین، پیچیدگی فضایی این الگوریتم برابر با $\mathrm{O}\left({\mathrm{n}}^{\mathrm{2}}\right)$ است.