Cari laluan terpendek antara mana-mana dua nod menggunakan algoritma Floyd-Warshal

C++ mempunyai makro, yang ditakrifkan sebagai sekeping kod atau nilai yang dijangkakan, dan ia akan digunakan semula pada bila-bila masa pengguna memerlukannya. Algoritma Floyd-Walshall ialah proses mencari laluan terpendek antara semua pasangan bucu dalam graf berwajaran tertentu. Algoritma mengikut pendekatan pengaturcaraan dinamik untuk mencari graf berat minimum.

Mari kita fahami maksud Algoritma Freud-Walshire melalui gambar rajah -

Dengan bucu 1 sebagai sumber dan bucu 4 sebagai destinasi, cari jalan terpendek di antara mereka.

Kami telah melihat bahawa terdapat dua laluan yang boleh disambungkan ke puncak sasaran 4.

• 1 -> 4 – Tepi mempunyai berat 5

• 1 -> 8 -> 3 ->

Dalam graf I yang diberikan, kita melihat tepi minimum yang menghubungkan dua bucu. Jadi di sini laluan dari bucu 8 ke bucu 3 menghubungkan bucu 1 ke bucu 4 dan tepi ialah 4. Sebaliknya, terdapat tepi terarah dari bucu 1 ke bucu 4, dan berat tepi ialah 5.

Sekarang kita bandingkan dua pemberat iaitu 4 dan 5. Oleh itu, di sini 4 ialah berat minimum graf yang dikira mengikut algoritma Floyd Warshall.

Dalam artikel ini, kami akan menggunakan algoritma Floyd Warshall untuk mencari laluan terpendek antara mana-mana dua nod yang diberikan.

Tatabahasa

Sintaks berikut digunakan dalam program -

data_type[][] array_name;

Parameter

data_type[][] - Jenis data yang disebut oleh pengguna. Tatasusunan pertama mewakili baris dan tatasusunan kedua mewakili lajur. Jadi, ini mewakili tatasusunan dua dimensi.

array_name - Nama yang diberikan kepada array.

Algoritma

• Kami akan memulakan program dengan fail pengepala 'iostream' dan mentakrifkan lokasi makro sebagai 'INF' (infiniti) kerana kemudiannya ia akan memenuhi matriks tatasusunan 2D dan pernyataan if-else.

• Seterusnya, kami mencipta definisi fungsi global yang dipanggil 'printPath' dan menerima tiga parameter, 'parent[]', 'i' dan 'j' untuk mengesahkan bahawa laluan itu wujud.

• Kemudian kita mulakan fungsi utama dan simpan nilai ‘4’ ke dalam pembolehubah ‘V’, yang mewakili bilangan bucu. Kedua, simpan nilai dalam bentuk matriks bersebelahan ke dalam pembolehubah ‘dist[V][V]’. Seperti yang kita ketahui, dist[i][j] mewakili matriks 2D, yang mentakrifkan berat tepi daripada ‘i’ hingga ‘j’, dengan menyimpan matriks bersebelahan.

• Seterusnya, kami memulakan tatasusunan 2D untuk pembolehubah ‘induk’, dengan saiz [V][V].

Dalam pembolehubah ini kita gunakan untuk memaparkan setiap pasangan bucu 'i' dan 'j' w.r.t 'ibu bapa[i][j]'.

• Dengan menggunakan dua gelung bersarang kita akan mencari laluan terpendek. Gelung untuk pertama berulang ke atas baris dalam matriks. Kemudian, ulangi lajur dalam matriks melalui gelung kedua untuk dan kemudian kami akan menyemak keadaan berikut menggunakan pernyataan if-else -

• Jika (dist[i][j] != INF && i != j) { Terjemahan bahasa Cina bagi ibu bapa[i][j] = i;}

  ialah: ibu bapa[i][j] = i;}

  Dalam pernyataan if, kami menggunakan operator 'and' (&&) untuk menyatakan dua syarat jika kedua-dua syarat dipenuhi, maka 'i' akan disimpan ke dalam 'parent[i][j]' , dengan itu mengesahkan bahawa. jalan itu wujud.

• Lain-lain{ Terjemahan bahasa Cina bagi parent[i][j] = -1;}

  ialah: parent[i][j] = -1;}

  Dalam pernyataan else, kami memulakan "-1" kepada "ibu bapa[i][j]" untuk mengesahkan bahawa laluan itu tidak wujud.

• Kini kita mulakan dengan tiga gelung untuk bersarang dan menggunakan bucu k dalam julat dari 0 hingga V-1, dengan bantuan julat ini jarak dan laluan terpendek kita akan dikemas kini. Dalam gelung bersarang ketiga kami menggunakan keadaan berikut seperti

if (dist[i][j] < dist[i][k] + dist[k][j]){
   dist[i][j] = dist[i][k] + dist[k][j]; 
   parent[i][j] = parent[k][j];	
}

Di sini K sedang mengemas kini bahagian baris dan lajur matriks tatasusunan 2D, yang mengesahkan laluan dan jarak terpendek yang baru dikemas kini.

• Seterusnya, kami mencetak jarak dan laluan terpendek bagi semua pasangan bucu dengan memberikan syarat berikut

• Dengan menggunakan dua gelung bersarang, kami mencetak jarak dan laluan terpendek.

• Dengan menggunakan pernyataan if di bawah gelung kedua untuk, kami akan menyemak sama ada dist[i][j] bersamaan dengan infiniti. Jika ia didapati infiniti, cetak "INF", jika tidak cetak laluan terpendek.

• Akhir sekali, kami memanggil fungsi yang dipanggil 'printPath()' dengan melepasi tiga parameter (induk [i], i dan j.

Contoh

Dalam program ini, kami akan menggunakan algoritma Floyd Warshall untuk mengira laluan terpendek antara mana-mana dua nod.

#include <iostream> 
using namespace std; 
#define INF 1000000000 // Infinity

void printPath(int parent[], int i, int j) {
   if (i == j) 
      cout << i << " "; 
   else if (parent[j] == -1) 
     cout << "No path exists"; 
   else
   { 
      printPath(parent, i, parent[j]); 
      cout << j << " "; 
   }
} 

int main() 
{
   int V = 4; 
   // V represent number of vertices
   int dist[V][V] = {{0, 2, INF, 4}, 
      {6, 0, 5, 3}, 
      {INF, 10, 0, 1}, 
      {7, 9, 8, 0}}; 
   // Represent the graph using adjacency matrix

   // Apply the Floyd Warshall algorithm to find the shortest paths
   int parent[V][V];
   for (int i = 0; i < V; i++) 
   { 
      for (int j = 0; j < V; j++) 
      {
         if (dist[i][j] != INF && i != j)
         parent[i][j] = i;
         else
         parent[i][j] = -1;
      }
   }
   // update the path and distance using the k vertex range from 0 to V-1.
   for (int k = 0; k < V; k++) 
   { 
      for (int i = 0; i < V; i++) 
      { 
         for (int j = 0; j < V; j++) 
         { 
            if (dist[i][j] > dist[i][k] + dist[k][j]) 
            {
               dist[i][j] = dist[i][k] + dist[k][j];
               parent[i][j] = parent[k][j];	
            }
         }
      }
   }

   // Print shortest distances and paths between all pairs of vertices
   for (int i = 0; i < V; i++) 
   { 
      for (int j = 0; j < V; j++) 
      { 
         cout << "The Shortest distance between " << i << " and " << j << " is ";
         if (dist[i][j] == INF) 
            cout << "INF "; 
         else
            cout << dist[i][j] << " ";

         cout << "and the shortest path is:- ";
         printPath(parent[i], i, j);
         cout << endl;
      } 
   } 

   return 0; 
}

输出

The Shortest distance between 0 and 0 is 0 and the shortest path is:- 0 
The Shortest distance between 0 and 1 is 2 and the shortest path is:- 0 1 
The Shortest distance between 0 and 2 is 7 and the shortest path is:- 0 1 2 
The Shortest distance between 0 and 3 is 4 and the shortest path is:- 0 3 
The Shortest distance between 1 and 0 is 6 and the shortest path is:- 1 0 
The Shortest distance between 1 and 1 is 0 and the shortest path is:- 1 
The Shortest distance between 1 and 2 is 5 and the shortest path is:- 1 2 
The Shortest distance between 1 and 3 is 3 and the shortest path is:- 1 3 
The Shortest distance between 2 and 0 is 8 and the shortest path is:- 2 3 0 
The Shortest distance between 2 and 1 is 10 and the shortest path is:- 2 1 
The Shortest distance between 2 and 2 is 0 and the shortest path is:- 2 
The Shortest distance between 2 and 3 is 1 and the shortest path is:- 2 3 
The Shortest distance between 3 and 0 is 7 and the shortest path is:- 3 0 
The Shortest distance between 3 and 1 is 9 and the shortest path is:- 3 1 
The Shortest distance between 3 and 2 is 8 and the shortest path is:- 3 2 
The Shortest distance between 3 and 3 is 0 and the shortest path is:- 3 

结论

我们学习了使用Floyd Warshall算法找到任意两个节点之间的最短路径的概念。我们使用邻接矩阵作为程序的输入，通过它我们找到了最短路径和距离。此外，为了更新路径和距离，我们使用了k个顶点来更新行和列。在我们的日常生活中，我们在谷歌地图上搜索最短路线或路径，从一个起点到目的地。

Atas ialah kandungan terperinci Cari laluan terpendek antara mana-mana dua nod menggunakan algoritma Floyd-Warshal. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!