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

1// C++ Program for Floyd Warshall Algorithm  
2#include <bits/stdc++.h> 
3using namespace std; 
4  
5// Number of vertices in the graph  
6#define V 4  
7  
8/* Define Infinite as a large enough 
9value.This value will be used for  
10vertices not connected to each other */
11#define INF 99999  
12  
13// A function to print the solution matrix  
14void printSolution(int dist[][V]);  
15  
16// Solves the all-pairs shortest path  
17// problem using Floyd Warshall algorithm  
18void floydWarshall (int graph[][V])  
19{  
20    /* dist[][] will be the output matrix  
21    that will finally have the shortest  
22    distances between every pair of vertices */
23    int dist[V][V], i, j, k;  
24  
25    /* Initialize the solution matrix same  
26    as input graph matrix. Or we can say  
27    the initial values of shortest distances 
28    are based on shortest paths considering  
29    no intermediate vertex. */
30    for (i = 0; i < V; i++)  
31        for (j = 0; j < V; j++)  
32            dist[i][j] = graph[i][j];  
33  
34    /* Add all vertices one by one to  
35    the set of intermediate vertices.  
36    ---> Before start of an iteration,  
37    we have shortest distances between all  
38    pairs of vertices such that the  
39    shortest distances consider only the  
40    vertices in set {0, 1, 2, .. k-1} as 
41    intermediate vertices.  
42    ----> After the end of an iteration,  
43    vertex no. k is added to the set of  
44    intermediate vertices and the set becomes {0, 1, 2, .. k} */
45    for (k = 0; k < V; k++)  
46    {  
47        // Pick all vertices as source one by one  
48        for (i = 0; i < V; i++)  
49        {  
50            // Pick all vertices as destination for the  
51            // above picked source  
52            for (j = 0; j < V; j++)  
53            {  
54                // If vertex k is on the shortest path from  
55                // i to j, then update the value of dist[i][j]  
56                if (dist[i][k] + dist[k][j] < dist[i][j])  
57                    dist[i][j] = dist[i][k] + dist[k][j];  
58            }  
59        }  
60    }  
61  
62    // Print the shortest distance matrix  
63    printSolution(dist);  
64}  
65  
66/* A utility function to print solution */
67void printSolution(int dist[][V])  
68{  
69    cout<<"The following matrix shows the shortest distances"
70            " between every pair of vertices \n";  
71    for (int i = 0; i < V; i++)  
72    {  
73        for (int j = 0; j < V; j++)  
74        {  
75            if (dist[i][j] == INF)  
76                cout<<"INF"<<"     ";  
77            else
78                cout<<dist[i][j]<<"     ";  
79        }  
80        cout<<endl;  
81    }  
82}  
83  
84// Driver code  
85int main()  
86{  
87    /* Let us create the following weighted graph  
88            10  
89    (0)------->(3)  
90        |     /|\  
91    5 |     |  
92        |     | 1  
93    \|/     |  
94    (1)------->(2)  
95            3     */
96    int graph[V][V] = { {0, 5, INF, 10},  
97                        {INF, 0, 3, INF},  
98                        {INF, INF, 0, 1},  
99                        {INF, INF, INF, 0}  
100                    };  
101  
102    // Print the solution  
103    floydWarshall(graph);  
104    return 0;  
105}  
106  
107// This code is contributed by rathbhupendra 

1// C Program for Floyd Warshall Algorithm 
2#include<stdio.h> 
3  
4// Number of vertices in the graph 
5#define V 4 
6  
7/* Define Infinite as a large enough value. This value will be used 
8  for vertices not connected to each other */
9#define INF 99999 
10  
11// A function to print the solution matrix 
12void printSolution(int dist[][V]); 
13  
14// Solves the all-pairs shortest path problem using Floyd Warshall algorithm 
15void floydWarshall (int graph[][V]) 
16{ 
17    /* dist[][] will be the output matrix that will finally have the shortest  
18      distances between every pair of vertices */
19    int dist[V][V], i, j, k; 
20  
21    /* Initialize the solution matrix same as input graph matrix. Or  
22       we can say the initial values of shortest distances are based 
23       on shortest paths considering no intermediate vertex. */
24    for (i = 0; i < V; i++) 
25        for (j = 0; j < V; j++) 
26            dist[i][j] = graph[i][j]; 
27  
28    /* Add all vertices one by one to the set of intermediate vertices. 
29      ---> Before start of an iteration, we have shortest distances between all 
30      pairs of vertices such that the shortest distances consider only the 
31      vertices in set {0, 1, 2, .. k-1} as intermediate vertices. 
32      ----> After the end of an iteration, vertex no. k is added to the set of 
33      intermediate vertices and the set becomes {0, 1, 2, .. k} */
34    for (k = 0; k < V; k++) 
35    { 
36        // Pick all vertices as source one by one 
37        for (i = 0; i < V; i++) 
38        { 
39            // Pick all vertices as destination for the 
40            // above picked source 
41            for (j = 0; j < V; j++) 
42            { 
43                // If vertex k is on the shortest path from 
44                // i to j, then update the value of dist[i][j] 
45                if (dist[i][k] + dist[k][j] < dist[i][j]) 
46                    dist[i][j] = dist[i][k] + dist[k][j]; 
47            } 
48        } 
49    } 
50  
51    // Print the shortest distance matrix 
52    printSolution(dist); 
53} 
54  
55/* A utility function to print solution */
56void printSolution(int dist[][V]) 
57{ 
58    printf ("The following matrix shows the shortest distances"
59            " between every pair of vertices \n"); 
60    for (int i = 0; i < V; i++) 
61    { 
62        for (int j = 0; j < V; j++) 
63        { 
64            if (dist[i][j] == INF) 
65                printf("%7s", "INF"); 
66            else
67                printf ("%7d", dist[i][j]); 
68        } 
69        printf("\n"); 
70    } 
71} 
72  
73// driver program to test above function 
74int main() 
75{ 
76    /* Let us create the following weighted graph 
77            10 
78       (0)------->(3) 
79        |         /|\ 
80      5 |          | 
81        |          | 1 
82       \|/         | 
83       (1)------->(2) 
84            3           */
85    int graph[V][V] = { {0,   5,  INF, 10}, 
86                        {INF, 0,   3, INF}, 
87                        {INF, INF, 0,   1}, 
88                        {INF, INF, INF, 0} 
89                      }; 
90  
91    // Print the solution 
92    floydWarshall(graph); 
93    return 0; 
94}

1// A Java program for Floyd Warshall All Pairs Shortest 
2// Path algorithm. 
3import java.util.*; 
4import java.lang.*; 
5import java.io.*; 
6  
7  
8class AllPairShortestPath 
9{ 
10    final static int INF = 99999, V = 4; 
11  
12    void floydWarshall(int graph[][]) 
13    { 
14        int dist[][] = new int[V][V]; 
15        int i, j, k; 
16  
17        /* Initialize the solution matrix same as input graph matrix. 
18           Or we can say the initial values of shortest distances 
19           are based on shortest paths considering no intermediate 
20           vertex. */
21        for (i = 0; i < V; i++) 
22            for (j = 0; j < V; j++) 
23                dist[i][j] = graph[i][j]; 
24  
25        /* Add all vertices one by one to the set of intermediate 
26           vertices. 
27          ---> Before start of an iteration, we have shortest 
28               distances between all pairs of vertices such that 
29               the shortest distances consider only the vertices in 
30               set {0, 1, 2, .. k-1} as intermediate vertices. 
31          ----> After the end of an iteration, vertex no. k is added 
32                to the set of intermediate vertices and the set 
33                becomes {0, 1, 2, .. k} */
34        for (k = 0; k < V; k++) 
35        { 
36            // Pick all vertices as source one by one 
37            for (i = 0; i < V; i++) 
38            { 
39                // Pick all vertices as destination for the 
40                // above picked source 
41                for (j = 0; j < V; j++) 
42                { 
43                    // If vertex k is on the shortest path from 
44                    // i to j, then update the value of dist[i][j] 
45                    if (dist[i][k] + dist[k][j] < dist[i][j]) 
46                        dist[i][j] = dist[i][k] + dist[k][j]; 
47                } 
48            } 
49        } 
50  
51        // Print the shortest distance matrix 
52        printSolution(dist); 
53    } 
54  
55    void printSolution(int dist[][]) 
56    { 
57        System.out.println("The following matrix shows the shortest "+ 
58                         "distances between every pair of vertices"); 
59        for (int i=0; i<V; ++i) 
60        { 
61            for (int j=0; j<V; ++j) 
62            { 
63                if (dist[i][j]==INF) 
64                    System.out.print("INF "); 
65                else
66                    System.out.print(dist[i][j]+"   "); 
67            } 
68            System.out.println(); 
69        } 
70    } 
71  
72    // Driver program to test above function 
73    public static void main (String[] args) 
74    { 
75        /* Let us create the following weighted graph 
76           10 
77        (0)------->(3) 
78        |         /|\ 
79        5 |          | 
80        |          | 1 
81        \|/         | 
82        (1)------->(2) 
83           3           */
84        int graph[][] = { {0,   5,  INF, 10}, 
85                          {INF, 0,   3, INF}, 
86                          {INF, INF, 0,   1}, 
87                          {INF, INF, INF, 0} 
88                        }; 
89        AllPairShortestPath a = new AllPairShortestPath(); 
90  
91        // Print the solution 
92        a.floydWarshall(graph); 
93    } 
94} 
95  
96// Contributed by Aakash Hasija

1V = 4
2INF = 99999
3
4def floydWarshall(graph):
5    dist = list(map(lambda i : map(lambda j : j , i) , graph))
6    for k in range(V):
7        # pick all vertices as source one by one
8        for i in range(V):
9            for j in range(V):
10                dist[i][j] = min(dist[i][j] ,dist[i][k]+ dist[k][j] )
11    printSolution(dist)
12
13def printSolution(dist):
14    print ("Following matrix shows the shortest distances between every pair of vertices")
15    for i in range(V):
16        for j in range(V):
17            if(dist[i][j] == INF):
18                print ("%7s" %("INF"),)
19            else:
20                print ("%7d\t" %(dist[i][j]),)
21            if j == V-1:
22                print ("")
23                graph = [[0,5,INF,10],
24                         [INF,0,3,INF],
25                         [INF, INF, 0,   1],
26                         [INF, INF, INF, 0]
27                        ]
28floydWarshall(graph);
29python

1// A C# program for Floyd Warshall All  
2// Pairs Shortest Path algorithm. 
3  
4using System; 
5  
6public class AllPairShortestPath 
7{ 
8    readonly static int INF = 99999, V = 4; 
9  
10    void floydWarshall(int[,] graph) 
11    { 
12        int[,] dist = new int[V, V]; 
13        int i, j, k; 
14  
15        // Initialize the solution matrix  
16        // same as input graph matrix 
17        // Or we can say the initial  
18        // values of shortest distances 
19        // are based on shortest paths  
20        // considering no intermediate 
21        // vertex 
22        for (i = 0; i < V; i++) { 
23            for (j = 0; j < V; j++) { 
24                dist[i, j] = graph[i, j]; 
25            } 
26        } 
27  
28        /* Add all vertices one by one to  
29        the set of intermediate vertices. 
30        ---> Before start of a iteration, 
31             we have shortest distances 
32             between all pairs of vertices 
33             such that the shortest distances 
34             consider only the vertices in 
35             set {0, 1, 2, .. k-1} as  
36             intermediate vertices. 
37        ---> After the end of a iteration,  
38             vertex no. k is added 
39             to the set of intermediate 
40             vertices and the set 
41             becomes {0, 1, 2, .. k} */
42        for (k = 0; k < V; k++) 
43        { 
44            // Pick all vertices as source 
45            // one by one 
46            for (i = 0; i < V; i++) 
47            { 
48                // Pick all vertices as destination 
49                // for the above picked source 
50                for (j = 0; j < V; j++) 
51                { 
52                    // If vertex k is on the shortest 
53                    // path from i to j, then update 
54                    // the value of dist[i][j] 
55                    if (dist[i, k] + dist[k, j] < dist[i, j])  
56                    { 
57                        dist[i, j] = dist[i, k] + dist[k, j]; 
58                    } 
59                } 
60            } 
61        } 
62  
63        // Print the shortest distance matrix 
64        printSolution(dist); 
65    } 
66  
67    void printSolution(int[,] dist) 
68    { 
69        Console.WriteLine("Following matrix shows the shortest "+ 
70                        "distances between every pair of vertices"); 
71        for (int i = 0; i < V; ++i) 
72        { 
73            for (int j = 0; j < V; ++j) 
74            { 
75                if (dist[i, j] == INF) { 
76                    Console.Write("INF "); 
77                } else { 
78                    Console.Write(dist[i, j] + " "); 
79                } 
80            } 
81              
82            Console.WriteLine(); 
83        } 
84    } 
85  
86    // Driver Code 
87    public static void Main(string[] args) 
88    { 
89        /* Let us create the following 
90           weighted graph 
91              10 
92        (0)------->(3) 
93        |         /|\ 
94        5 |         | 
95        |         | 1 
96        \|/         | 
97        (1)------->(2) 
98             3             */
99        int[,] graph = { {0, 5, INF, 10}, 
100                        {INF, 0, 3, INF}, 
101                        {INF, INF, 0, 1}, 
102                        {INF, INF, INF, 0} 
103                        }; 
104          
105        AllPairShortestPath a = new AllPairShortestPath(); 
106  
107        // Print the solution 
108        a.floydWarshall(graph); 
109    } 
110} 
111  
112// This article is contributed by  
113// Abdul Mateen Mohammed

1<?php 
2// PHP Program for Floyd Warshall Algorithm  
3  
4// Solves the all-pairs shortest path problem 
5// using Floyd Warshall algorithm  
6function floydWarshall ($graph, $V, $INF)  
7{  
8    /* dist[][] will be the output matrix  
9    that will finally have the shortest  
10    distances between every pair of vertices */
11    $dist = array(array(0,0,0,0), 
12                  array(0,0,0,0), 
13                  array(0,0,0,0), 
14                  array(0,0,0,0)); 
15  
16    /* Initialize the solution matrix same  
17    as input graph matrix. Or we can say the  
18    initial values of shortest distances are  
19    based on shortest paths considering no  
20    intermediate vertex. */
21    for ($i = 0; $i < $V; $i++)  
22        for ($j = 0; $j < $V; $j++)  
23            $dist[$i][$j] = $graph[$i][$j];  
24  
25    /* Add all vertices one by one to the set  
26    of intermediate vertices.  
27    ---> Before start of an iteration, we have  
28    shortest distances between all pairs of  
29    vertices such that the shortest distances  
30    consider only the vertices in set  
31    {0, 1, 2, .. k-1} as intermediate vertices.  
32    ----> After the end of an iteration, vertex  
33    no. k is added to the set of intermediate 
34    vertices and the set becomes {0, 1, 2, .. k} */
35    for ($k = 0; $k < $V; $k++)  
36    {  
37        // Pick all vertices as source one by one  
38        for ($i = 0; $i < $V; $i++)  
39        {  
40            // Pick all vertices as destination  
41            // for the above picked source  
42            for ($j = 0; $j < $V; $j++)  
43            {  
44                // If vertex k is on the shortest path from  
45                // i to j, then update the value of dist[i][j]  
46                if ($dist[$i][$k] + $dist[$k][$j] <  
47                                    $dist[$i][$j])  
48                    $dist[$i][$j] = $dist[$i][$k] + 
49                                    $dist[$k][$j];  
50            }  
51        }  
52    }  
53  
54    // Print the shortest distance matrix  
55    printSolution($dist, $V, $INF);  
56}  
57  
58/* A utility function to print solution */
59function printSolution($dist, $V, $INF)  
60{  
61    echo "The following matrix shows the " . 
62             "shortest distances between " .  
63                "every pair of vertices \n";  
64    for ($i = 0; $i < $V; $i++)  
65    {  
66        for ($j = 0; $j < $V; $j++)  
67        {  
68            if ($dist[$i][$j] == $INF)  
69                echo "INF " ;  
70            else
71                echo $dist[$i][$j], " "; 
72        }  
73        echo "\n";  
74    }  
75}  
76  
77// Driver Code 
78  
79// Number of vertices in the graph  
80$V = 4 ; 
81  
82/* Define Infinite as a large enough  
83value. This value will be used for 
84vertices not connected to each other */
85$INF = 99999 ; 
86  
87/* Let us create the following weighted graph  
88        10  
89(0)------->(3)  
90    |     /|\  
915 |     |  
92    |     | 1  
93\|/     |  
94(1)------->(2)  
95        3     */
96$graph = array(array(0, 5, $INF, 10),  
97               array($INF, 0, 3, $INF),  
98               array($INF, $INF, 0, 1),  
99               array($INF, $INF, $INF, 0));  
100  
101// Print the solution  
102floydWarshall($graph, $V, $INF);  
103  
104// This code is contributed by Ryuga 
105?>