informasi kontak saya
Surat[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Daftar isi
Algoritma Floyd, nama lengkap dari algoritma Floyd-Warshall, merupakan algoritma pemrograman dinamis yang digunakan untuk menyelesaikan masalah jalur terpendek antara semua pasangan simpul pada grafik. Cocok untuk graf berarah berbobot dan dapat menangani sisi berbobot negatif (tetapi tidak untuk graf yang mengandung siklus berbobot negatif), dan dapat mendeteksi apakah terdapat siklus berbobot negatif pada grafik.
Ide inti dari algoritma Floyd adalah pemrograman dinamis, dan langkah dasarnya adalah sebagai berikut:
Implementasi algoritma Floyd biasanya menggunakan loop rangkap tiga. Loop luar melintasi semua simpul perantara k, dan dua loop dalam melintasi semua pasangan simpul (i, j) untuk memeriksa apakah terdapat jalur yang lebih pendek.
Misalkan kita mempunyai graf berbobot G yang memuat n simpul, kita dapat menggunakan array dua dimensidist[][]
untuk menyimpan panjang jalur terpendek antara setiap pasangan simpul. Mulanya,dist[i][j]
diatur ke bobot sisi yang terhubung langsung pada grafik. Jika tidak ada sisi yang terhubung langsung antara i dan j, makadist[i][j]
Atur ke tak terhingga (menunjukkan tidak dapat dijangkau).
inisialisasi : Buat matriks D berukuran n×n, dengan D[i][j] diinisialisasi dengan bobot sisi lurus dari i ke j pada grafik, atau disetel ke tak terhingga jika tidak ada sisi langsung antara i dan j. Elemen diagonal D[i][i] = 0.
pemrograman dinamis : Untuk setiap simpul k (sebagai simpul perantara), perbarui jalur terpendek antara setiap pasangan simpul i dan j. Jalur yang lebih pendek dapat diperoleh dengan k sebagai titik perantara. Rumus pembaruannya adalah: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). Artinya jika jalur dari i ke j menjadi lebih pendek melalui k sebagai titik perantara, perbarui D[i][j].
Keluaran hasil: Setelah n putaran iterasi, setiap elemen D[i][j] pada matriks D merupakan panjang jalur terpendek dari i ke j.
343. Penyortiran - Bank Soal AcWing
- #include <algorithm>
- #include <bits/stdc++.h>
- #include <iostream>
- using namespace std;
-
- #define PII pair<int, int>
- #define fi first
- #define se second
- #define endl 'n'
- map<int, int> mp;
-
- const int N = 210, mod = 1e9 + 7;
- int T, n, m, k;
- int a[N], dist[N][N];
- PII ans[N];
-
- void floyd(int x) // 以 x 为中转点,更新其他点。
- {
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
- }
-
- bool pd() // 判断是否所有点都已确定
- {
- for (int i = 1; i <= n; i++) {
- int cnt = 0;
- for (int j = 1; j <= n; j++)
- if (dist[i][j] != 1e9)
- cnt++; // 当前点能到达的点数
- ans[i] = {cnt, i};
- for (int j = 1; j <= n; j++)
- if (i != j && dist[j][i] != 1e9)
- cnt++; // 能到达当前点的点数
- if (cnt != n)
- return 0;
- }
- sort(ans + 1, ans + n + 1);
- return 1;
- }
-
- int main() {
- while (cin >> n >> m && n) {
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- if (i != j)
- dist[i][j] = 1e9;
-
- int flag = 0;
- for (int i = 1; i <= m; i++) {
- char a, t, b;
- cin >> a >> t >> b;
- int x = a - 'A' + 1, y = b - 'A' + 1; // 现在要加一条从 y 到 x 的边
-
- if (!flag && dist[x][y] != 1e9) // 发现已经从x能到y,出现矛盾
- {
- printf("Inconsistency found after %d relations.n", i);
- flag = 1;
- }
-
- dist[y][x] = 1;
- floyd(x), floyd(y); // 分别以 x 和 y 为中转点更新其他点
- if (!flag && pd()) { // 发现所有点都已确定
- printf("Sorted sequence determined after %d relations: ", i);
- for (int i = 1; i <= n; i++)
- cout << char(ans[i].se + 'A' - 1);
- printf(".n");
- flag = 1;
- }
- }
- if (!flag)
- printf("Sorted sequence cannot be determined.n"); // 无法确定
- }
-
- return 0;
- }
dist
Array dua dimensi diinisialisasi hingga tak terhingga, yang berarti tidak ada hubungan keteraturan pasti antara pertidaksamaan secara default.dist
Matrix, menggunakan algoritma Floyd untuk memperbarui jalur terpendek antara semua ketidaksetaraan, sebenarnya memperbarui hubungan "prioritas" atau "urutan".