Berbagi teknologi

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Daftar isi

Algoritma Floyd

definisi

Penggunaan

Tindakan pencegahan

Ide pemecahan masalah

Langkah-langkah dasar

AcWing 343. Penyortiran

Deskripsi pertanyaan

menjalankan kode

Ide kode

Tingkatkan ide

Algoritma Floyd

definisi

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.

Penggunaan

1. Hitung jalur terpendek antara semua pasangan simpul: Dalam bidang seperti analisis jaringan sosial, perencanaan jaringan transportasi, desain jaringan komunikasi, dll., algoritma Floyd adalah pilihan yang baik ketika diperlukan untuk menghitung jarak terpendek antara dua titik.
2. Deteksi siklus bobot negatif: Dalam beberapa skenario aplikasi, penting untuk memastikan bahwa tidak ada siklus bobot negatif dalam grafik, karena hal ini mungkin menunjukkan beberapa keadaan tidak normal atau kesalahan dalam sistem.

Tindakan pencegahan

• konsumsi memori : Kompleksitas ruang pada algoritma Floyd adalah O(n^2), dimana n adalah jumlah simpul pada grafik. Untuk grafik berskala besar, hal ini dapat menjadi masalah.
• kompleksitas waktu: Kompleksitas waktu algoritma Floyd adalah O(n^3). Ketika jumlah simpul banyak, algoritma mungkin menjadi sangat lambat.
• lingkaran bobot negatif : Jika terdapat siklus bobot negatif pada grafik, algoritma Floyd akan jatuh ke dalam loop tak terbatas, karena dimulai dari sebuah node, panjang jalur dapat dikurangi tanpa batas melalui siklus ini. Dalam penerapan praktis, situasi seperti itu perlu dideteksi dan ditangani terlebih dahulu.
• Algoritma dapat mendeteksi siklus bobot negatif:Jika pada saat eksekusi algoritma ditemukan bahwa jalur terpendek dari suatu simpul ke simpul itu sendiri kurang dari 0, yaitu D[i][i] < 0, maka paling sedikit terdapat satu siklus bobot negatif pada graf tersebut, dan algoritme tidak dapat memberikan hasil jalur terpendek yang benar saat ini.
• Untuk grafik yang sangat besar, kompleksitas waktu dan kompleksitas ruang yang tinggi dari algoritme mungkin menjadi hambatan. Saat ini, Anda mungkin perlu mempertimbangkan algoritme yang lebih efisien atau menggunakan struktur data dan teknik pengoptimalan yang lebih profesional.

Ide pemecahan masalah

Ide inti dari algoritma Floyd adalah pemrograman dinamis, dan langkah dasarnya adalah sebagai berikut:

1. Inisialisasi: Atur matriks jarak D ke matriks ketetanggaan grafik, yaitu D[i][j] = bobot(i, j); untuk i != j, jika (i, j) tidak terhubung, maka D[saya][j] = ∞; D[saya][saya] = 0.
2. Pemrograman dinamis: Untuk k = 1 hingga n, perbarui D sedemikian rupa sehingga D[i][j] = min(D[i][j], D[i][k] + D[k][j]), sehingga adalah Periksa apakah jarak dari i ke j dapat diperpendek melalui simpul perantara k.
3. Hasil: Matriks D akhir berisi panjang jalur terpendek antara semua pasangan simpul. Jika terjadi D[i][j] < 0 dan i != j tertentu, dan D[i][i] < 0 terjadi pada saat proses update, berarti terdapat siklus bobot negatif pada grafik.

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.

Langkah-langkah dasar

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).

1. 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.

2. 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].

3. Keluaran hasil: Setelah n putaran iterasi, setiap elemen D[i][j] pada matriks D merupakan panjang jalur terpendek dari i ke j.

AcWing 343. Penyortiran

Deskripsi pertanyaan

343. Penyortiran - Bank Soal AcWing

menjalankan kode

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

Ide kode

1. inisialisasi: GunakandistArray dua dimensi diinisialisasi hingga tak terhingga, yang berarti tidak ada hubungan keteraturan pasti antara pertidaksamaan secara default.
2. Baca masukan: Membaca hubungan dari input standar dalam format "B > A", yang menunjukkan bahwa B lebih baik dari A.
3. Pemrosesan hubungan:
   • Ketika suatu hubungan baru dibaca, diperiksa apakah ada kontradiksi (yaitu hubungan yang ditentukan sebelumnya bertentangan dengan hubungan baru).
   • memperbaruidistMatrix, menggunakan algoritma Floyd untuk memperbarui jalur terpendek antara semua ketidaksetaraan, sebenarnya memperbarui hubungan "prioritas" atau "urutan".
4. Periksa kepastian penyortiran:
   • Periksa apakah semua pertidaksamaan saling berhubungan, yaitu setiap titik dapat mencapai titik lainnya dan panjang lintasannya tidak berhingga.
   • Jika penyortiran ditemukan selama proses membaca hubungan, atau penyortiran masih tidak dapat ditentukan setelah membaca semua hubungan, informasi terkait akan ditampilkan.

Tingkatkan ide

• Peningkatan efisiensi : Panggilan floyd saat ini dilakukan segera setelah setiap hubungan baru ditambahkan, yang mungkin tidak diperlukan. Anda dapat menunggu sampai semua hubungan telah dibaca sebelum menjalankan kembali algoritma Floyd untuk mengurangi perhitungan yang tidak perlu.
• Sederhanakan logikanya : Kode saat ini lebih kompleks dalam mendeteksi kontradiksi dan menentukan logika penyelesaian pengurutan. Anda dapat mencoba menyederhanakan logikanya, seperti menggunakan struktur data yang lebih intuitif atau langkah algoritmik untuk memeriksa kondisi ini.
• kejelasan kode: Dapat meningkatkan kejelasan komentar dan struktur kode, membuat kode lebih mudah dipahami dan dipelihara.