फ्लोयड-वॉरसॉल एल्गोरिथम

इस ट्यूटोरियल में, आप सीखेंगे कि फ्लोयड-वॉरशेल एल्गोरिथ्म कैसे काम करता है। इसके अलावा, आप C, C ++, जावा और पायथन में फ्लोयड-वारशॉल एल्गोरिथ्म के काम करने के उदाहरण पाएंगे।

फ्लोयड-वारशॉल एल्गोरिथ्म एक भारित ग्राफ में सभी जोड़े के बीच सबसे छोटा रास्ता खोजने के लिए एक एल्गोरिथ्म है। यह एल्गोरिथ्म निर्देशित और अप्रत्यक्ष भारित रेखांकन दोनों के लिए काम करता है। लेकिन, यह नकारात्मक चक्रों के साथ रेखांकन के लिए काम नहीं करता है (जहां एक चक्र में किनारों का योग ऋणात्मक है)।

एक भारित ग्राफ एक ग्राफ है जिसमें प्रत्येक किनारे के साथ एक संख्यात्मक मूल्य जुड़ा होता है।

फ़्लॉइड-वारशश एल्गोरिथ्म को फ़्लॉइड्स एल्गोरिथ्म, रॉय-फ़्लॉइड एल्गोरिथ्म, रॉय-वारशॉल एल्गोरिथ्म या एफएफआई एल्गोरिथम भी कहा जाता है।

यह एल्गोरिथम सबसे छोटे रास्तों को खोजने के लिए गतिशील प्रोग्रामिंग दृष्टिकोण का अनुसरण करता है।

फ़्लॉइड-वॉरसॉल एल्गोरिथम कैसे काम करता है?

दिए गए ग्राफ को बताइए:

प्रारंभिक ग्राफ

सभी जोड़ों के बीच सबसे छोटा रास्ता खोजने के लिए नीचे दिए गए चरणों का पालन करें।

  1. आयाम का एक मैट्रिक्स बनाएं जहां n कोने की संख्या है। पंक्ति और स्तंभ को क्रमशः i और j के रूप में अनुक्रमित किया जाता है। मैं और जम्मू ग्राफ के कोने हैं। प्रत्येक कोशिका A (i) (j) को शिखर से शिखर की दूरी से भरा जाता है । यदि शीर्ष से शिखर तक कोई रास्ता नहीं है , तो सेल को अनंत के रूप में छोड़ दिया जाता है। Ith और jth vertex के बीच की दूरी के साथ प्रत्येक सेल भरेंA0n*n
    ithjthithjth
  2. अब, मैट्रिक्स का उपयोग करके एक मैट्रिक्स बनाएं । पहले कॉलम और पहली पंक्ति के तत्व जैसे हैं वैसे ही रह गए हैं। शेष कोशिकाओं को निम्नलिखित तरीके से भरा जाता है। आज्ञा देना गंतव्य के लिए सबसे कम पथ में मध्यवर्ती मध्यवर्ती शीर्ष होना चाहिए। इस चरण में, k पहला वर्टेक्स है। से भरा है । यही है, यदि स्रोत से गंतव्य तक सीधी दूरी, शीर्ष के कश्मीर के माध्यम से पथ से अधिक है, तो सेल से भर जाता है । इस चरण में, k शीर्ष 1 है। हम इस शीर्ष k के माध्यम से स्रोत शीर्ष से गंतव्य गंतव्य तक की दूरी की गणना करते हैं। स्रोत शीर्ष से दूरी की गणना करें इस शीर्ष के माध्यम से गंतव्य शीर्ष पर जाएं k उदाहरण के लिए: के लिएA1A0
    A(i)(j)(A(i)(k) + A(k)(j)) if (A(i)(j)> A(i)(k) + A(k)(j))
    A(i)(k) + A(k)(j)

    A1(2, 4), 4 के लिए शीर्ष 2 से सीधे दूरी (शीर्ष 2 से 1 करने के लिए और शीर्ष 1 से 4 के लिए अर्थात्।) 4 और 4 के लिए शीर्ष 2 से दूरी का योग शीर्ष के माध्यम से 7 के बाद से है 4 < 7, 4 से भर जाता है।A0(2, 4)
  3. इसी तरह, का उपयोग करके बनाया गया है । दूसरे स्तंभ और दूसरी पंक्ति के तत्व वैसे ही रह गए हैं जैसे वे हैं। इस चरण में, k दूसरा वर्टेक्स (यानी शीर्ष 2) है। शेष चरण चरण 2 में समान हैं । इस शीर्ष 2 के माध्यम से स्रोत शीर्ष से गंतव्य गंतव्य तक की दूरी की गणना करेंA2A3
  4. इसी तरह, और बनाया भी जाता है। इस शीर्ष 3 के माध्यम से स्रोत शीर्ष से गंतव्य शिखर तक की दूरी की गणना करें 3 इस शीर्ष 4 के माध्यम से स्रोत शीर्ष से गंतव्य शीर्ष की दूरी की गणना करेंA3A4
  5. A4 प्रत्येक जोड़ी के बीच सबसे छोटा रास्ता देता है।

फ्लोयड-वॉरसॉल एल्गोरिथम

n = संख्याओं का नहीं A = आयाम का मैट्रिक्स n * n के लिए k = 1 से n के लिए i = 1 से n के लिए j = 1 से n A k (i, j) = मिनट (A k-1 (i, j)) , A k-1 (i, k) + A k-1 (k, j)) A वापस करें

पायथन, जावा और सी / सी ++ उदाहरण

पायथन जावा सी सी ++ 
 # 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 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 C #include // 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(""); ) ) 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 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(""); ) ) int main() ( int graph(nV)(nV) = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)); floydWarshall(graph); )

फ्लोयड वॉरशेल एलगोरिदम जटिलता

समय जटिलता

तीन लूप हैं। प्रत्येक लूप में निरंतर जटिलताएं होती हैं। तो, फ्लोयड-वारशॉल एल्गोरिथ्म की समय जटिलता है ।O(n3)

अंतरिक्ष की जटिलता

फ़्लॉइड-वारशॉल एल्गोरिथ्म की अंतरिक्ष जटिलता है ।O(n2)

फ्लोयड वॉरसॉल एल्गोरिथ्म एप्लीकेशन

  • सबसे छोटा रास्ता खोजने के लिए एक निर्देशित ग्राफ है
  • निर्देशित रेखांकन के सकर्मक समापन को खोजने के लिए
  • वास्तविक मैट्रिसेस के व्युत्क्रम को खोजने के लिए
  • परीक्षण के लिए कि क्या एक अप्रत्यक्ष ग्राफ द्विदलीय है

दिलचस्प लेख...