الگوریتم فلوید وارشال (Floyd Warshall) — راهنمای کاربردی

در علوم کامپیوتر، «الگوریتم فلوید وارشال» (Floyd Warshall Algorithm) که با اسامی «الگوریتم فلوید» (Floyd's Algorithm)، «الگوریتم روی وارشال» (Roy–Warshall Algorithm)، «الگوریتم روی فلوید» (Roy–Floyd Algorithm) یا «الگوریتم دابلیواف‌آی» (WFI Algorithm) نیز شناخته شده است، از جمله الگوریتم‌های پیدا کردن کوتاه‌ترین مسیر در گراف وزن‌دار با وزن یال‌های مثبت یا منفی محسوب می‌شود (اما چرخه منفی وجود ندارد).

یک اجرای الگوریتم منجر به پیدا کردن طول‌های (مجموع وزن‌ها) کوتاه‌ترین مسیر بین همه جفت یال‌ها می‌شود. اگرچه، این مورد منجر به بازگرداندن جزئیاتی از خود مسیرها نمی‌شود، ولی این امکان وجود دارد که مسیرها با ویرایش‌های کوچکی در الگوریتم، بازسازی شوند. از نسخه‌های گوناگون این الگوریتم می‌توان برای پیدا کردن بستار تعدی رابطه R یا (در ارتباط با روش شولتسه) بزرگترین مسیر بین همه جفت یال‌ها در گراف وزن‌دار استفاده کرد.

در این مطلب، روش نوشتن برنامه الگوریتم فلوید وارشال بیان و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل «سی» (C)، «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ پی» (PHP) انجام شده است.

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

الگوریتم فلوید وارشال برای یافتن همه جفت کوتاه‌ترین مسیرها است. در واقع، مسئله پیدا کردن کوتاه‌ترین فاصله بین هر جفت از راس‌ها در گراف جهت‌دار وزن‌دار است. مثال زیر برای درک بهتر مطلب، قابل توجه است.

فیلم آموزش طراحی الگوریتم در فرادرس

کلیک کنید

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

ورودی به صورت زیر است.

graph[][] = { {0,   5,  INF, 10},
                    {INF,  0,  3,  INF},
                    {INF, INF, 0,   1},
                    {INF, INF, INF, 0} }

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

             10
       (0)------->(3)
        |         /|\
      5 |          |
        |          | 1
       \|/         |
       (1)------->(2)
            3

شایان توجه است که مقدار graph[i][j]‎ در صورتی که i برابر با j باشد، مساوی صفر است و اگر هیچ یالی از راس i به j وجود نداشته باشد، graph[i][j]‎ بی‌نهایت است. ماتریس کوتاه‌ترین مسیرها به صورت زیر است.

    0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0

الگوریتم فلوید وارشال

ابتدا ماتریس پاسخ با مقادیر موجود در ماتریس گراف ورودی، مقداردهی اولیه می‌شود. سپس، ماتریس خروجی با در نظر گرفتن همه راس‌ها به عنوان یک راس میانی، به روز رسانی می‌شود. هدف، پیدا کردن یک به یک رأس‌ها و به روز رسانی همه کوتاه‌ترین مسیرهایی است که شامل راس‌های انتخاب شده به عنوان راس میانی در کوتاه‌ترین مسیر می‌شوند.

فیلم آموزش طراحی الگوریتم + حل مثال های عملی در فرادرس

کلیک کنید

هنگامی که رأس شماره k به عنوان یک راس میانی انتخاب می‌شود، پیش‌تر، رأس‌های $$\left\{0, 1, 2, .. k-1\right\}$$ به عنوان راس‌های میانی انتخاب شده‌اند. برای هر جفت (i, j) از رأس‌های مبدأ و مقصد، دو حالت ممکن وجود دارد.

1. k یک رأس میانی در کوتاه‌ترین مسیر از i به j نیست. مقدار dist[i][j]‎ به صورتی که هست، حفظ می‌شود.
2. k یک رأس میانی در کوتاه‌ترین مسیر از i به j است. اگر dist[i][j] > dist[i][k] + dist[k][j]‎، مقادیر dist[i][j]‎ به صورت dist[i][k] + dist[k][j]‎ به روز رسانی می‌شود.

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

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

الگوریتم فلوید وارشال در ++C

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس C++‎ در فرادرس

کلیک کنید

// C++ Program for Floyd Warshall Algorithm  
#include <bits/stdc++.h> 
using namespace std; 
  
// Number of vertices in the graph  
#define V 4  
  
/* Define Infinite as a large enough 
value.This value will be used for  
vertices not connected to each other */
#define INF 99999  
  
// A function to print the solution matrix  
void printSolution(int dist[][V]);  
  
// Solves the all-pairs shortest path  
// problem using Floyd Warshall algorithm  
void floydWarshall (int graph[][V])  
{  
    /* dist[][] will be the output matrix  
    that will finally have the shortest  
    distances between every pair of vertices */
    int dist[V][V], i, j, k;  
  
    /* Initialize the solution matrix same  
    as input graph matrix. Or we can say  
    the initial values of shortest distances 
    are based on shortest paths considering  
    no intermediate vertex. */
    for (i = 0; i < V; i++)  
        for (j = 0; j < V; j++)  
            dist[i][j] = graph[i][j];  
  
    /* Add all vertices one by one to  
    the set of intermediate vertices.  
    ---> Before start of an iteration,  
    we have shortest distances between all  
    pairs of vertices such that the  
    shortest distances consider only the  
    vertices in set {0, 1, 2, .. k-1} as 
    intermediate vertices.  
    ----> After the end of an iteration,  
    vertex no. k is added to the set of  
    intermediate vertices and the set becomes {0, 1, 2, .. k} */
    for (k = 0; k < V; k++)  
    {  
        // Pick all vertices as source one by one  
        for (i = 0; i < V; i++)  
        {  
            // Pick all vertices as destination for the  
            // above picked source  
            for (j = 0; j < V; j++)  
            {  
                // If vertex k is on the shortest path from  
                // i to j, then update the value of dist[i][j]  
                if (dist[i][k] + dist[k][j] < dist[i][j])  
                    dist[i][j] = dist[i][k] + dist[k][j];  
            }  
        }  
    }  
  
    // Print the shortest distance matrix  
    printSolution(dist);  
}  
  
/* A utility function to print solution */
void printSolution(int dist[][V])  
{  
    cout<<"The following matrix shows the shortest distances"
            " between every pair of vertices \n";  
    for (int i = 0; i < V; i++)  
    {  
        for (int j = 0; j < V; j++)  
        {  
            if (dist[i][j] == INF)  
                cout<<"INF"<<"     ";  
            else
                cout<<dist[i][j]<<"     ";  
        }  
        cout<<endl;  
    }  
}  
  
// Driver code  
int main()  
{  
    /* Let us create the following weighted graph  
            10  
    (0)------->(3)  
        |     /|\  
    5 |     |  
        |     | 1  
    \|/     |  
    (1)------->(2)  
            3     */
    int graph[V][V] = { {0, 5, INF, 10},  
                        {INF, 0, 3, INF},  
                        {INF, INF, 0, 1},  
                        {INF, INF, INF, 0}  
                    };  
  
    // Print the solution  
    floydWarshall(graph);  
    return 0;  
}  
  
// This code is contributed by rathbhupendra 

الگوریتم فلوید وارشال در C

فیلم آموزش ساختمان داده ها در فرادرس

کلیک کنید

// C Program for Floyd Warshall Algorithm 
#include<stdio.h> 
  
// Number of vertices in the graph 
#define V 4 
  
/* Define Infinite as a large enough value. This value will be used 
  for vertices not connected to each other */
#define INF 99999 
  
// A function to print the solution matrix 
void printSolution(int dist[][V]); 
  
// Solves the all-pairs shortest path problem using Floyd Warshall algorithm 
void floydWarshall (int graph[][V]) 
{ 
    /* dist[][] will be the output matrix that will finally have the shortest  
      distances between every pair of vertices */
    int dist[V][V], i, j, k; 
  
    /* Initialize the solution matrix same as input graph matrix. Or  
       we can say the initial values of shortest distances are based 
       on shortest paths considering no intermediate vertex. */
    for (i = 0; i < V; i++) 
        for (j = 0; j < V; j++) 
            dist[i][j] = graph[i][j]; 
  
    /* Add all vertices one by one to the set of intermediate vertices. 
      ---> Before start of an iteration, we have shortest distances between all 
      pairs of vertices such that the shortest distances consider only the 
      vertices in set {0, 1, 2, .. k-1} as intermediate vertices. 
      ----> After the end of an iteration, vertex no. k is added to the set of 
      intermediate vertices and the set becomes {0, 1, 2, .. k} */
    for (k = 0; k < V; k++) 
    { 
        // Pick all vertices as source one by one 
        for (i = 0; i < V; i++) 
        { 
            // Pick all vertices as destination for the 
            // above picked source 
            for (j = 0; j < V; j++) 
            { 
                // If vertex k is on the shortest path from 
                // i to j, then update the value of dist[i][j] 
                if (dist[i][k] + dist[k][j] < dist[i][j]) 
                    dist[i][j] = dist[i][k] + dist[k][j]; 
            } 
        } 
    } 
  
    // Print the shortest distance matrix 
    printSolution(dist); 
} 
  
/* A utility function to print solution */
void printSolution(int dist[][V]) 
{ 
    printf ("The following matrix shows the shortest distances"
            " between every pair of vertices \n"); 
    for (int i = 0; i < V; i++) 
    { 
        for (int j = 0; j < V; j++) 
        { 
            if (dist[i][j] == INF) 
                printf("%7s", "INF"); 
            else
                printf ("%7d", dist[i][j]); 
        } 
        printf("\n"); 
    } 
} 
  
// driver program to test above function 
int main() 
{ 
    /* Let us create the following weighted graph 
            10 
       (0)------->(3) 
        |         /|\ 
      5 |          | 
        |          | 1 
       \|/         | 
       (1)------->(2) 
            3           */
    int graph[V][V] = { {0,   5,  INF, 10}, 
                        {INF, 0,   3, INF}, 
                        {INF, INF, 0,   1}, 
                        {INF, INF, INF, 0} 
                      }; 
  
    // Print the solution 
    floydWarshall(graph); 
    return 0; 
}

الگوریتم فلوید وارشال در جاوا

فیلم آموزش برنامه نویسی جاوا Java در فرادرس

کلیک کنید

// A Java program for Floyd Warshall All Pairs Shortest 
// Path algorithm. 
import java.util.*; 
import java.lang.*; 
import java.io.*; 
  
  
class AllPairShortestPath 
{ 
    final static int INF = 99999, V = 4; 
  
    void floydWarshall(int graph[][]) 
    { 
        int dist[][] = new int[V][V]; 
        int i, j, k; 
  
        /* Initialize the solution matrix same as input graph matrix. 
           Or we can say the initial values of shortest distances 
           are based on shortest paths considering no intermediate 
           vertex. */
        for (i = 0; i < V; i++) 
            for (j = 0; j < V; j++) 
                dist[i][j] = graph[i][j]; 
  
        /* Add all vertices one by one to the set of intermediate 
           vertices. 
          ---> Before start of an iteration, we have shortest 
               distances between all pairs of vertices such that 
               the shortest distances consider only the vertices in 
               set {0, 1, 2, .. k-1} as intermediate vertices. 
          ----> After the end of an iteration, vertex no. k is added 
                to the set of intermediate vertices and the set 
                becomes {0, 1, 2, .. k} */
        for (k = 0; k < V; k++) 
        { 
            // Pick all vertices as source one by one 
            for (i = 0; i < V; i++) 
            { 
                // Pick all vertices as destination for the 
                // above picked source 
                for (j = 0; j < V; j++) 
                { 
                    // If vertex k is on the shortest path from 
                    // i to j, then update the value of dist[i][j] 
                    if (dist[i][k] + dist[k][j] < dist[i][j]) 
                        dist[i][j] = dist[i][k] + dist[k][j]; 
                } 
            } 
        } 
  
        // Print the shortest distance matrix 
        printSolution(dist); 
    } 
  
    void printSolution(int dist[][]) 
    { 
        System.out.println("The following matrix shows the shortest "+ 
                         "distances between every pair of vertices"); 
        for (int i=0; i<V; ++i) 
        { 
            for (int j=0; j<V; ++j) 
            { 
                if (dist[i][j]==INF) 
                    System.out.print("INF "); 
                else
                    System.out.print(dist[i][j]+"   "); 
            } 
            System.out.println(); 
        } 
    } 
  
    // Driver program to test above function 
    public static void main (String[] args) 
    { 
        /* Let us create the following weighted graph 
           10 
        (0)------->(3) 
        |         /|\ 
        5 |          | 
        |          | 1 
        \|/         | 
        (1)------->(2) 
           3           */
        int graph[][] = { {0,   5,  INF, 10}, 
                          {INF, 0,   3, INF}, 
                          {INF, INF, 0,   1}, 
                          {INF, INF, INF, 0} 
                        }; 
        AllPairShortestPath a = new AllPairShortestPath(); 
  
        // Print the solution 
        a.floydWarshall(graph); 
    } 
} 
  
// Contributed by Aakash Hasija

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

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

کلیک کنید

V = 4
INF = 99999

def floydWarshall(graph):
    dist = list(map(lambda i : map(lambda j : j , i) , graph))
    for k in range(V):
        # pick all vertices as source one by one
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j] ,dist[i][k]+ dist[k][j] )
    printSolution(dist)

def printSolution(dist):
    print ("Following matrix shows the shortest distances between every pair of vertices")
    for i in range(V):
        for j in range(V):
            if(dist[i][j] == INF):
                print ("%7s" %("INF"),)
            else:
                print ("%7d\t" %(dist[i][j]),)
            if j == V-1:
                print ("")
                graph = [[0,5,INF,10],
                         [INF,0,3,INF],
                         [INF, INF, 0,   1],
                         [INF, INF, INF, 0]
                        ]
floydWarshall(graph);
python

الگوریتم فلوید وارشال در C#‎

فیلم آموزش طراحی الگوریتم در فرادرس

کلیک کنید

// A C# program for Floyd Warshall All  
// Pairs Shortest Path algorithm. 
  
using System; 
  
public class AllPairShortestPath 
{ 
    readonly static int INF = 99999, V = 4; 
  
    void floydWarshall(int[,] graph) 
    { 
        int[,] dist = new int[V, V]; 
        int i, j, k; 
  
        // Initialize the solution matrix  
        // same as input graph matrix 
        // Or we can say the initial  
        // values of shortest distances 
        // are based on shortest paths  
        // considering no intermediate 
        // vertex 
        for (i = 0; i < V; i++) { 
            for (j = 0; j < V; j++) { 
                dist[i, j] = graph[i, j]; 
            } 
        } 
  
        /* Add all vertices one by one to  
        the set of intermediate vertices. 
        ---> Before start of a iteration, 
             we have shortest distances 
             between all pairs of vertices 
             such that the shortest distances 
             consider only the vertices in 
             set {0, 1, 2, .. k-1} as  
             intermediate vertices. 
        ---> After the end of a iteration,  
             vertex no. k is added 
             to the set of intermediate 
             vertices and the set 
             becomes {0, 1, 2, .. k} */
        for (k = 0; k < V; k++) 
        { 
            // Pick all vertices as source 
            // one by one 
            for (i = 0; i < V; i++) 
            { 
                // Pick all vertices as destination 
                // for the above picked source 
                for (j = 0; j < V; j++) 
                { 
                    // If vertex k is on the shortest 
                    // path from i to j, then update 
                    // the value of dist[i][j] 
                    if (dist[i, k] + dist[k, j] < dist[i, j])  
                    { 
                        dist[i, j] = dist[i, k] + dist[k, j]; 
                    } 
                } 
            } 
        } 
  
        // Print the shortest distance matrix 
        printSolution(dist); 
    } 
  
    void printSolution(int[,] dist) 
    { 
        Console.WriteLine("Following matrix shows the shortest "+ 
                        "distances between every pair of vertices"); 
        for (int i = 0; i < V; ++i) 
        { 
            for (int j = 0; j < V; ++j) 
            { 
                if (dist[i, j] == INF) { 
                    Console.Write("INF "); 
                } else { 
                    Console.Write(dist[i, j] + " "); 
                } 
            } 
              
            Console.WriteLine(); 
        } 
    } 
  
    // Driver Code 
    public static void Main(string[] args) 
    { 
        /* Let us create the following 
           weighted graph 
              10 
        (0)------->(3) 
        |         /|\ 
        5 |         | 
        |         | 1 
        \|/         | 
        (1)------->(2) 
             3             */
        int[,] graph = { {0, 5, INF, 10}, 
                        {INF, 0, 3, INF}, 
                        {INF, INF, 0, 1}, 
                        {INF, INF, INF, 0} 
                        }; 
          
        AllPairShortestPath a = new AllPairShortestPath(); 
  
        // Print the solution 
        a.floydWarshall(graph); 
    } 
} 
  
// This article is contributed by  
// Abdul Mateen Mohammed

الگوریتم فلوید وارشال در PHP

فیلم آموزش طراحی الگوریتم + حل مثال های عملی در فرادرس

کلیک کنید

<?php 
// PHP Program for Floyd Warshall Algorithm  
  
// Solves the all-pairs shortest path problem 
// using Floyd Warshall algorithm  
function floydWarshall ($graph, $V, $INF)  
{  
    /* dist[][] will be the output matrix  
    that will finally have the shortest  
    distances between every pair of vertices */
    $dist = array(array(0,0,0,0), 
                  array(0,0,0,0), 
                  array(0,0,0,0), 
                  array(0,0,0,0)); 
  
    /* Initialize the solution matrix same  
    as input graph matrix. Or we can say the  
    initial values of shortest distances are  
    based on shortest paths considering no  
    intermediate vertex. */
    for ($i = 0; $i < $V; $i++)  
        for ($j = 0; $j < $V; $j++)  
            $dist[$i][$j] = $graph[$i][$j];  
  
    /* Add all vertices one by one to the set  
    of intermediate vertices.  
    ---> Before start of an iteration, we have  
    shortest distances between all pairs of  
    vertices such that the shortest distances  
    consider only the vertices in set  
    {0, 1, 2, .. k-1} as intermediate vertices.  
    ----> After the end of an iteration, vertex  
    no. k is added to the set of intermediate 
    vertices and the set becomes {0, 1, 2, .. k} */
    for ($k = 0; $k < $V; $k++)  
    {  
        // Pick all vertices as source one by one  
        for ($i = 0; $i < $V; $i++)  
        {  
            // Pick all vertices as destination  
            // for the above picked source  
            for ($j = 0; $j < $V; $j++)  
            {  
                // If vertex k is on the shortest path from  
                // i to j, then update the value of dist[i][j]  
                if ($dist[$i][$k] + $dist[$k][$j] <  
                                    $dist[$i][$j])  
                    $dist[$i][$j] = $dist[$i][$k] + 
                                    $dist[$k][$j];  
            }  
        }  
    }  
  
    // Print the shortest distance matrix  
    printSolution($dist, $V, $INF);  
}  
  
/* A utility function to print solution */
function printSolution($dist, $V, $INF)  
{  
    echo "The following matrix shows the " . 
             "shortest distances between " .  
                "every pair of vertices \n";  
    for ($i = 0; $i < $V; $i++)  
    {  
        for ($j = 0; $j < $V; $j++)  
        {  
            if ($dist[$i][$j] == $INF)  
                echo "INF " ;  
            else
                echo $dist[$i][$j], " "; 
        }  
        echo "\n";  
    }  
}  
  
// Driver Code 
  
// Number of vertices in the graph  
$V = 4 ; 
  
/* Define Infinite as a large enough  
value. This value will be used for 
vertices not connected to each other */
$INF = 99999 ; 
  
/* Let us create the following weighted graph  
        10  
(0)------->(3)  
    |     /|\  
5 |     |  
    |     | 1  
\|/     |  
(1)------->(2)  
        3     */
$graph = array(array(0, 5, $INF, 10),  
               array($INF, 0, 3, $INF),  
               array($INF, $INF, 0, 1),  
               array($INF, $INF, $INF, 0));  
  
// Print the solution  
floydWarshall($graph, $V, $INF);  
  
// This code is contributed by Ryuga 
?>

خروجی قطعه کدهای بالا به صورت زیر است.

Following matrix shows the shortest distances between every pair of vertices
      0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0

پیچیدگی زمانی روش بالا از درجه O(V³)‎ است. برنامه بالا، فقط کوتاه‌ترین مسیر را چاپ می‌کند. می‌توان این برنامه را به گونه‌ای ویرایش کرد که کوتاه‌ترین مسیرها را با ذخیره‌سازی اطلاعات اجداد آن‌ها در یک ماتریس دوبُعدی، نمایش دهد. همچنین، مقدار INF (بی‌نهایت) را می‌توان از limits.h به عنوان INT_MAX به دست آورد تا اطمینان حاصل شود که با بزرگ‌ترین مقدار ممکن کار شده است. هنگامی که INF به عنوان INT_MAX قرار داده می‌شود، نیاز به تغییر شرط if در برنامه بالا است تا از سرریز محاسباتی جلوگیری شود.

#include 

#define INF INT_MAX
..........................
if ( dist[i][k] != INF && 
     dist[k][j] != INF && 
     dist[i][k] + dist[k][j] < dist[i][j]
    )
 dist[i][j] = dist[i][k] + dist[k][j];
...........................

فیلم مجموعه آموزش ساختمان داده و طراحی الگوریتم در فرادرس

کلیک کنید

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
• الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
• الگوریتم پریم — به زبان ساده
• متن کاوی (Text Mining) — به زبان ساده

^^