Floyd Warshall Algorithm in Hindi – DAA

Hello दोस्तों आज मैं आपको इस आर्टिकल में Floyd Warshall Algorithm in Hindi (फ्लॉयड वार्शल अल्गोरिथ्म क्या है?) के बारें में बताऊंगा और इसके उदाहरण को भी देखेंगे तो चलिए शुरू करते हैं:-

Floyd Warshall Algorithm in Hindi

Floyd warshall algorithm एक algorithm है इसका प्रयोग weighted graph में negative या positive edge weights के साथ shortest path को खोजने के लिए किया जाता है.

दूसरे शब्दों में कहें तो, “Floyd-Warshall अल्गोरिथ्म एक weighted graph में vertices के सभी pairs के मध्य shortest path खोजने की एक algorithm है.”

यह अल्गोरिथ्म directed और undirected दोनों graphs के लिए काम करती है. इस algorithm को  Floyd’s algorithm, Roy-Floyd algorithm, Roy-Warshall algorithm, या WFI algorithm भी कहते हैं.

यह अल्गोरिथ्म shortest path को ढूंडने के लिए dynamic programming एप्रोच को follow करता है.

Algorithm:-

  1. n = rows [W]
  2.  D ^ (0) = W
  3. For k = 1 to n
  4. Do for I = 1 to n
  5.  Do for j = 1 to n
  6. d (ij) ^ (k) = min (d(ij) ^ (k-1), d (ik) ^ (k-1) + d(kj) ^ (k-1))
  7. return D ^ (n)

Applications of Floyd Warshall Algorithm in Hindi

इसके अनुप्रयोग निम्नलिखित हैं:-

  1. इसका प्रयोग directed graph में shortest path को खोजने के लिए किया जाता है.
  2. directed graphs के transitive closure को find करने के लिए.
  3. real matrices के inversion को find करने के लिए.
  4. इसका प्रयोग यह test करने के लिए भी किया जाता है कि कहीं undirected ग्राफ bipartite तो नहीं है.

इसका C language का example:-

#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);
}

निवेदन:- अगर आपके लिए यह पोस्ट थोड़ी सी भी helpful रही हो तो इसे अपने friends के साथ अवश्य share कीजिये और आपके जो भी questions हैं आप उन्हें नीचे comment करके बता सकते हैं.

Leave a Comment