در علوم کامپیوتر، «الگوریتم فلوید وارشال» (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-1right}$$ به عنوان راسهای میانی انتخاب شدهاند. برای هر جفت (i, j) از رأسهای مبدأ و مقصد، دو حالت ممکن وجود دارد.
- k یک رأس میانی در کوتاهترین مسیر از i به j نیست. مقدار dist[i][j] به صورتی که هست، حفظ میشود.
- k یک رأس میانی در کوتاهترین مسیر از i به j است. اگر dist[i][j] > dist[i][k] + dist[k][j]، مقادیر dist[i][j] به صورت dist[i][k] + dist[k][j] به روز رسانی میشود.
تصویری که در ادامه آمده است، نشاندهنده خصوصیات زیر ساختار بهینه بالا در مسئله کوتاهترین مسیر برای همه جفتها است.
در ادامه، پیادهسازی الگوریتم فلوید وارشال در زبانهای برنامهنویسی گوناگون انجام شده است.
الگوریتم فلوید وارشال در ++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);
retu 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);
retu 0;
}
الگوریتم فلوید وارشال در جاوا
// 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
الگوریتم فلوید وارشال در پایتون
# Python Program for Floyd Warshall Algorithm
# Number of vertices in the graph
V = 4
# Define infinity as the large enough value. This value will be
# used for vertices not connected to each other
INF = 99999
# Solves all pair shortest path via Floyd Warshall Algorithm
def floydWarshall(graph):
""" dist[][] will be the output matrix that will finally
have the shortest distances between every pair of vertices """
""" initializing the solution matrix same as input graph matrix
OR we can say that the initial values of shortest distances
are based on shortest paths considering no
intermediate vertices """
dist = map(lambda i : map(lambda j : j , i) , graph)
""" 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 the 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 in range(V):
# pick all vertices as source one by one
for i in range(V):
# Pick all vertices as destination for the
# above picked source
for j in range(V):
# If vertex k is on the shortest path from
# i to j, then update the value of dist[i][j]
dist[i][j] = min(dist[i][j] ,
dist[i][k]+ dist[k][j]
)
printSolution(dist)
# A utility function to print the solution
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 "%7dt" %(dist[i][j]),
if j == V-1:
print ""
# Driver program to test the above program
# Let us create the following weighted graph
"""
10
(0)------->(3)
| /|
5 | |
| | 1
|/ |
(1)------->(2)
3 """
graph = [[0,5,INF,10],
[INF,0,3,INF],
[INF, INF, 0, 1],
[INF, INF, INF, 0]
]
# Print the solution
floydWarshall(graph);
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
الگوریتم فلوید وارشال در 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(V3) است. برنامه بالا، فقط کوتاهترین مسیر را چاپ میکند. میتوان این برنامه را به گونهای ویرایش کرد که کوتاهترین مسیرها را با ذخیرهسازی اطلاعات اجداد آنها در یک ماتریس دوبُعدی، نمایش دهد. همچنین، مقدار 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) — به زبان ساده
^^
