Algoritma Ford-Bellman
Mari kita diberi graf berwajaran terarah G dengan n bucu dan tepi m dan beberapa titik permulaan v . Ia diperlukan untuk mencari panjang laluan terpendek dari bucu v ke semua bucu lain.
Seperti Dijkstra, Ford-Bellman mencari jarak dari bucu 1 ke semua yang lain, tetapi berfungsi dengan tepi negatif< / kuat>.
Algoritma Ford-Bellman sendiri terdiri daripada beberapa fasa ( n-1). Pada setiap fasa, semua tepi graf diperiksa dan algoritma cuba berehat di sepanjang setiap tepi (a, b) kos c. Relaksasi di sepanjang tepi — ini adalah percubaan untuk menambah baik makna d[a] nilai d[b] + c. Malah, ini bermakna kami cuba menambah baik jawapan untuk bucu dengan menggunakan tepi dan jawapan semasa untuk bahagian atas.
Tatasusunan d ialah tatasusunan dengan panjang terpendek dari bucu permulaan, sama seperti dalam Dijkstra, kami pada mulanya mengisinya dengan nombor sebanyak mungkin, kecuali untuk bucu permulaan, di mana anda perlu meletakkan 0.
Untuk menyimpan tepi, bukan matriks bersebelahan atau matriks berat digunakan, tetapi senarai yang menunjukkan dari nod mana tepi meninggalkan ( dari), yang mana ia datang ( ke) dan beratnya (kos).
tepi struct {
int daripada, kepada, kos;
};
vektor<tepi> tepi;
Pemalar INF menandakan nombor "infiniti" - ia mesti dipilih dengan cara yang jelas melebihi semua panjang laluan yang mungkin.
Pelaksanaan algoritma yang paling mudah:
d[v] = 0;
untuk (int i=0; i<n-1; ++i)
untuk (int j=0; j<m; ++j)
jika (d[tepi[j].daripada] <INF)
d[tepi[j].kepada] = min(d[tepi[j].kepada], d[tepi[j].daripada] + tepi[j].kos);
atau pendek sedikit menggunakan sintaks C++11:
d[v] = 0;
untuk (int i=0; i< n-1; ++i)
untuk (tepi j: tepi)
jika (d[j.from] <INF)
d[j.to] = min(d[j.to], d[j.from] + j.kos);
Contoh kerja
Ambil graf terarah mudah dengan 5 nod, 4 tepi dengan berat bersamaan dengan 1.
Mari kita perkenalkan senarai tepi dalam susunan itu.
4 5 1
3 4 1
2 3 1
1 2 1
Nilai awal dalam tatasusunan panjang terpendek:
| 0 |
inf |
inf |
inf |
inf |
di mana inf mestilah integer sepadan yang sentiasa lebih besar daripada berat tepi.
Selepas lulus pertama
| 0 |
1 |
inf |
inf |
inf |
Selepas pas ke-2
| 0 |
1 |
2 |
inf |
inf |
Selepas pas ke-3
| 0 |
1 |
2 |
3 |
inf |
Selepas pas ke-4
| 0 |
1 |
2 |
3 |
4 |
Jika kita memasukkan tepi mengikut urutan dari 1 hingga terakhir, kita boleh mencari panjang terpendek selepas hantaran pertama.
|